## DMOJLand Series: Fake Judges

View as PDF

Points: 7 (partial)
Time limit: 1.0s
Memory limit: 64M

Author:
Problem type

In DMOJLand, when you submit a problem, you assume that a judge is grading a submission. In reality, it is the problem authors who assigned a specific point value for each person when they submit!

bruce has students in his class. When the person submits, they will gain a total of points, where .

Unfortunately, you are submitting to Ninjaclasher's problems, and he wants to minimize the total amount of points bruce's class will obtain.

During the class, the students will submit times to Ninjaclasher's problems. For the query, , students to will submit and earn their respective points, where the total points they obtain are , or .

Before all of the queries are performed, Ninjaclasher can move around the positions of as many students as he would like. Can you help him minimize the total sum of all the queries?

(TLDR; This is why you get low marks on quizzes.)

#### Input Specification

First line of input will contain 2 integers, and , the size of the class and the number of times the students will submit, respectively.

The second line of input will contain , for , the amount of points the student will obtain every time he submits.

The next lines of input will contain , denoting the range of the students that will submit.

#### Output Specification

Output the minimum possible sum.

#### Sample Input 1

4 3
1 2 3 4
2 3
1 4
1 2

#### Sample Output 1

17