题目描述

有一个小女孩非常喜欢数组查询类问题。

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

小女孩觉得这个问题太无聊了。她决定在回答所有查询前，先对数组的元素进行重新排序，使得所有查询结果的总和尽可能大。你的任务就是找到这个可能的最大总和。

输入格式

第一行包含两个用空格隔开的整数 $n$ 和 $q$，分别代表数组中元素的数量和查询的数量。

第二行包含 $n$ 个用空格隔开的整数 $a_i$，代表数组的元素。

接下来 $q$ 行，每行包含两个用空格隔开的整数 $l_i$ 和 $r_i$，代表一个查询。

输出格式

输出一个整数，表示在对数组元素进行最优重排后，所有查询结果的总和的最大值。

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

数据规模与约定

对于 $100\%$ 的数据，$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$。 请注意，最终答案可能会超过 32 位整型变量的存储范围，建议使用 64 位整型（例如 C++ 中的 long long）来存储结果。