Alice is having an array of N numbers (1-based indexing) and was playing with it by answering queries of the form $L,R$ where $1 \le L \le R \le N$. Query was simply sum of elements of the array with indexes from $L to R$ (Both inclusive).

In the mean time John, her younger brother came and rearrange all the elements of the array before she could reply to the queries.

Now if earlier the output of queries were $Q[1],Q[2]...$ Now it becomes $Q'[1],Q'[2]...$

The values of $Q'[1],Q'[2]...$ may still be same. But one thing good happen in all this incidence is the sum of all the queries become maximum that is $Q'[1]+Q'[2]+...$ is maximum . She is interested in finding this maximum value of sum.

Input Format:
First line consists of N integers and each q queries. Next line contains N elements presented in array. After this, the line consists of q queries, where each query is of form $L,R$.

Output Format:
We need to find the maximum sum of query replies after the array elements are rearranged .

Constraints :

$1 \le N \le 10^{5}$ $1 \le q \le 10^{5}$

Each array element is in range between $1 to 2·10^{5}$

Each query satisfies $1 \le L \le R \le N$