Logan and Queries

Interview

Time limit2sMemory limit1024 MB

Summary

Rearrange an array so that the total of all q range-sum query answers is as large as possible, then report that maximum sum.

Level: Medium4 of 10
Topics: Prefix sum, Greedy, Sorting
Solved: No attempts yet

Problem

Professor X has an array of $n$ numbers. He makes $q$ queries. Each query consists of two integers $l$ and $r$ , and its answer is the sum of the elements with indices from $l$ to $r$ in the original array.

Professor X's happiness level is the total of all query answers.

Logan wants to make Professor X as happy as possible. To do this, he may rearrange the elements of the array in any order.

He has not been able to manage this on his own, so he asked you for help.

Your task is to compute the maximum possible happiness level of Professor X when the elements of the array may be rearranged in any order.

Input

The first line contains two integers $n$ and $q$ ( $1 \leq n, q \leq 10^5$ ).

The second line contains $n$ integers $a_i$ ( $1 \leq a_i \leq 10^8$ ), the elements of the array.

Each of the next $q$ lines contains a pair of integers $l$ and $r$ ( $1 \leq l \leq r \leq n$ ), the bounds of a segment.

Output

Print one integer: the maximum possible happiness level of Professor X when the elements may be rearranged in any order.

Examples1

Example 1
Input
```
3 4
7 3 1
1 3
2 3
3 3
2 2
```
Expected output
```
31
```