Little Girl and Maximum Sum

题意翻译

有$n$个数字，为$a[1]\ ...\ a[n]$，$q$个询问。 每次读入$l,r$，询问$\sum_{i=l}^ra[i]$。 这样岂不是很水！ 于是你可以重新排列读入的$a$数组，使**询问的总和最大**。 输出这个最大值。 $n,q \le 2\times 10^5$ $1\le a_i \le 2 \times 10^5$ $1\le l_i \le r_i \le n$

题目描述

The little girl loves the problems on array queries very much. One day she came across a rather well-known problem: you've got an array of $ n $ elements (the elements of the array are indexed starting from 1); also, there are $ q $ queries, each one is defined by a pair of integers $ l_{i} $ , $ r_{i} $ $ (1<=l_{i}<=r_{i}<=n) $ . You need to find for each query the sum of elements of the array with indexes from $ l_{i} $ to $ r_{i} $ , inclusive. The little girl found the problem rather boring. She decided to reorder the array elements before replying to the queries in a way that makes the sum of query replies maximum possible. Your task is to find the value of this maximum sum.

输入输出格式

输入格式

The first line contains two space-separated integers $ n $ ( $ 1<=n<=2·10^{5} $ ) and $ q $ ( $ 1<=q<=2·10^{5} $ ) — the number of elements in the array and the number of queries, correspondingly. The next line contains $ n $ space-separated integers $ a_{i} $ ( $ 1<=a_{i}<=2·10^{5} $ ) — the array elements. Each of the following $ q $ lines contains two space-separated integers $ l_{i} $ and $ r_{i} $ ( $ 1<=l_{i}<=r_{i}<=n $ ) — the $ i $ -th query.

输出格式

In a single line print a single integer — the maximum sum of query replies after the array elements are reordered. Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.

输入输出样例

输入样例 #1

3 3
5 3 2
1 2
2 3
1 3

输出样例 #1

25

输入样例 #2

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

输出样例 #2

33