C. 小女孩与最大和

每次测试时间限制：$1$ 秒
内存限制：$256$ 兆字节

这个小女孩非常喜欢处理数组查询的问题。

有一天，她遇到了一个相当经典的问题：给定一个包含 $n$ 个元素的数组（数组元素从 $1$ 开始编号），有 $q$ 个查询，每个查询由一对整数 $l_i, r_i$ 定义（$1 \le l_i \le r_i \le n$）。对于每个查询，需要求出数组下标从 $l_i$ 到 $r_i$（包含两端）的元素之和。

小女孩觉得这个问题有点无聊。她决定，在回答查询之前重新排列数组元素的顺序，使得所有查询答案的总和尽可能大。你的任务是找出这个最大总和。

输入

第一行包含两个空格分隔的整数 $n$ 和 $q$（$1 \le n, q \le 2 \cdot 10^5$）——分别表示数组元素个数和查询个数。

第二行包含 $n$ 个空格分隔的整数 $a_i$（$1 \le a_i \le 2 \cdot 10^5$）——数组元素。

接下来的 $q$ 行，每行包含两个空格分隔的整数 $l_i$ 和 $r_i$（$1 \le l_i \le r_i \le n$）——第 $i$ 个查询。

输出

打印一行一个整数 —— 在重新排列数组元素后，所有查询答案的总和的最大可能值。

在 C++ 中，请勿使用 %lld 格式说明符来读写 $64$ 位整数。建议使用 cin、cout 流或 %I64d 格式说明符。

示例

示例 $1$

输入：

3 3
5 3 2
1 2
2 3
1 3

输出：

25

示例 $2$

输入：

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

输出：

33