← 返回题目列表

Codeforces · 276/C

C. 小女孩和最大总和

中文机器翻译题面 查看原题

小女孩非常喜欢数组查询的问题。

有一天,她遇到了一个相当著名的问题:你有一个 $$$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