题目描述

有 $n$ 个数字，为 $a_i$，$q$ 个询问。每次读入 $l,r$，询问 $∑_{i=l}^r a_i$。

这样岂不是很水！于是你可以重新排列读入的 $a$ 数组，使询问的总和最大。输出这个最大值。

输入格式

第一行两个整数 $n,q$，$1\le n,q\le 2\times 10^5$。

第二行 $n$ 个整数 $a_i$，$1\le a_i\le 2\times 10^5$。

接下来 $q$ 行，每行两个整数 $l,r$。

输出格式

输出一个整数表示答案。

3 3
5 3 2
1 2
2 3
1 3

25

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

33