DMOJLand Series: Fake Judges

View as PDF

Submit solution

Points: 7 (partial)
Time limit: 0.5s
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 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

Comments

There are no comments at the moment.