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 ~N~ students in his class. When the ~i^\text{th}~ person submits, they will gain a total of ~a_i~ points, where ~1 \le i \le N~.

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 ~Q~ times to Ninjaclasher's problems. For the ~q^\text{th}~ query, ~1 \le q \le N~, students ~l_j~ to ~r_j~ will submit and earn their respective points, where the total points they obtain are ~\sum_{j=l}^r A_j~, or ~A_l + A_{l+1} + \dots + A_r~.

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

Constraints

Subtask 1 [30%]

~1 \le N, Q, A_i \le 100~

~l_i = r_i~

Subtask 2 [70%]

No additional constraints.

Input Specification

The first line of input will contain 2 integers, ~N~ and ~Q~ ~(1 \le N, Q \le 10^5)~, the size of the class and the number of times the students will submit, respectively.

The second line of input will contain ~a_i~ ~(1 \le a_i \le 10^9)~, for ~1 \le i \le N~, the number of points the ~i^\text{th}~ student will obtain every time he submits.

The next ~Q~ lines of input will contain ~l_i~ ~r_i~, 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 ~5 \times 10^{18}~.

Sample Input 1

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

Sample Output 1

17