You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

有$n$个数字，为$a[1]\ ...\ a[n]$。

$q$个询问， 每个询问包含两个数字$l,r$，表示询问$\sum_{i=l}^ra[ i ]$。

温馨提示:$(\sum_{i=l}^ra[ i ]=a_l+a_{l+1}+a_{l+2}+...+a_{r-2}+a_{r-1}+a_r)$。

于是你可以重新排列给出的$a$数组，使这$q$组询问所得结果之和最大。

输出这个最大值。

输入格式

第一行输入 $n$ 和 $q$

第二行输入 $n$个数字，第i个数字为$a_i$

接下来 $q$行，每组询问占一行，包含两个数$l_i,r_i$

输出格式

一个数，即上述答案

样例

3 3
5 3 2
1 2
2 3
1 3

25

样例解释

我们让 $a$ 数组变成 2，5，3，结果就能得到最大值 25

数据范围

$1\le 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$