思路：排序+双指针

贪心，只要一座山峰的攀登时间达到了某种装备的最低适用时间，那么这座山就可以使用这种装备。

每座山一旦满足某种装备的最低适用时间，就可以使用该装备并获得对应的时间减少，因此我们需要为每座山选择可用装备中减少时间最大的。

攀登时间越长的山峰越能满足最低适用时间越高的装备，所以我们将装备和山峰都按时间从小到大排序。

然后按时间从小到大来枚举山峰，找到所有最低适用时间小于等于当前山峰攀登时间的装备，从中选出一个减少时间最大的，应用即可。

题目内容

你是一名登山者，计划攀登 $n$ 座山峰，第 $i$ 座山峰所需的攀登时间为 $t_i$。你有 $m$ 种专业登山装备，每种装备可以重复使用，但每座山只能选择其中一种装备。第 $j$ 种装备的使用条件为：如果一座山的攀登所需时间不低于 $x_j$，则可以使用该装备，使攀登时间减少 $y_j$。请问，通过合理选择装备，完成所有山峰攀登最少需要多少总时间？

数据范围：山峰数量 $n$ 与装备种类 $m$ 满足 $1 \le n, m \le 2 \times 10^5$；每座山的所需时间 $t_i$ 满足 $1 \le t_i \le 10^9$；装备参数满足 $1 \le y_j < x_j \le 10^9$。

输入描述

第一行包含两个整数 $n$ 和 $m$。 第二行包含 $n$ 个整数 $t_1, t_2, \dots, t_n$，表示每座山所需的攀登时间。 接下来 $m$ 行，每行包含两个整数 $x_j$ 和 $y_j$，分别表示第 $j$ 种装备的最低适用时间和可减少的时间。

输出描述

输出一个整数，表示最少总攀登时间。

样例1

输入

2 2
5 10
6 3
8 5

输出

10

说明

两座山的攀登所需时间分别为 $t_1 = 5$, $t_2 = 10$。装备有 $(6,3)$ 与 $(8,5)$。对时间排序后依次处理：

• 对于 $t_1 = 5$：没有装备满足 $x_j \le 5$（因为 $6 > 5$，$8 > 5$），无法使用任何装备，该山用时 5。
• 对于 $t_2 = 10$：所有装备均可使用，最大减少量 $\max(3,5) = 5$，用时 $10 - 5 = 5$。 总攀登时间为 $5 + 5 = 10$。

样例2

输入

3 4
3 7 8
4 2
4 3
5 1
7 4

输出

10

说明

攀登时间 $t = [3,7,8]$，装备参数为 $(4,2), (4,3), (5,1), (7,4)$。按 $t_i$ 升序处理：

• $t = 3$：无装备满足 $x_j \le 3$，用时 3。
• $t = 7$：满足条件的装备有 $(4,2),(4,3),(5,1),(7,4)$，其中最大 $y_j = 4$，用时 $7 - 4 = 3$。
• $t = 8$：所有装备同样满足条件，最大减少量仍为 $4$，用时 $8 - 4 = 4$。 总时间为 $3 + 3 + 4 = 10$。注意当 $x_j$ 相同时，应选取 $y_j$ 最大的装备（如 $(4,2)$ 与 $(4,3)$ 中选择 $y_j=3$）。

样例3

输入

3 2
1 1 1
2 1
3 2

输出

3

说明

每座山的攀登时间 $t_i = 1$（边界情况）。两种装备的最低适用时间分别为 $x_1 = 2$，$x_2 = 3$，均不满足 $x_j \le 1$，因此三座山都无法使用任何装备。总时间直接累加 $1 + 1 + 1 = 3$。