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!

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

hasUnfortunately, you are submitting to

's problems, and he wants to minimize the total amount of points 's class will obtain.During the class, the students will submit times to '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,

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.)

#### Constraints

##### Subtask 1 [30%]

##### Subtask 2 [70%]

No additional constraints.

#### Input Specification

The 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 number 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. It is guaranteed that this value will be at most .

#### Sample Input 1

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

#### Sample Output 1

`17`

## Comments