小女孩非常喜欢数组查询的问题。
有一天,她遇到了一个相当著名的问题:你有一个 $$$n$$$ 元素的数组(数组的元素从 1 开始索引);另外,还有 $$$q$$$ 查询,每个查询由一对整数 $$$l_i$$$、$$$r_i$$$ $$$(1 \le l_i \le r_i \le n)$$$ 定义。您需要为每个查询查找索引从 $$$l_i$$$ 到 $$$r_i$$$(含)的数组元素之和。
小女孩觉得这个问题很无聊。她决定在回复查询之前对数组元素重新排序,以使查询回复的总和尽可能最大。你的任务是找到这个最大总和的值。
输入
第一行包含两个空格分隔的整数 $$$n$$$ ($$$1 \le n \le 2\cdot10^5$$$) 和 $$$q$$$ ($$$1 \le q \le 2\cdot10^5$$$) — 相应地,数组中的元素数量和查询数量。
下一行包含 $$$n$$$ 空格分隔的整数 $$$a_i$$$ ($$$1 \le a_i \le 2\cdot10^5$$$) — 数组元素。
以下 $$$q$$$ 行均包含两个以空格分隔的整数 $$$l_i$$$ 和 $$$r_i$$$ ($$$1 \le l_i \le r_i \le n$$$) — 第 $$$i$$$ 个查询。
输出
在单行打印中,单个整数 — 数组元素重新排序后查询回复的最大总和。
请不要使用 %lld 说明符在 C++ 中读取或写入 64 位整数。最好使用 cin、cout 流或 %I64d 说明符。
示例
输入 #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