题目内容

在一款游戏中，共有 $n$ 位玩家和 $m$ 个挑战关卡。每位玩家拥有一个 extbf{能量值}，每个关卡设有一个 extbf{荣誉值}和一个 extbf{能量门槛}。只有当玩家的能量值不低于关卡的能量门槛时，才能挑战该关卡。

每位玩家至多选择一个关卡进行挑战，每个关卡也至多被一位玩家挑战。现在需要决定挑战安排，使得所有成功挑战的关卡荣誉值总和最大。请你计算这个最大值。

约束条件：玩家数量 $n$ 和关卡数量 $m$ 满足 $1 \le n, m \le 2 \times 10^5$。所有玩家的能量值、所有关卡的荣誉值和能量门槛均为不超过 $10^9$ 的正整数。

输入描述

第一行包含两个整数 $n$ 和 $m$，分别表示玩家数量和关卡数量。 第二行包含 $n$ 个整数，依次表示每位玩家的能量值。 接下来 $m$ 行，每行包含两个整数，依次表示一个关卡的荣誉值和能量门槛。

输出描述

输出一个整数，表示可以获得的最大荣誉值总和。

样例1

输入

2 2
10 20
8 10
5 15

输出

13

说明

共有 2 位朋友，金币数分别为 10 和 20；2 个房子，舒适度和价格分别为 $(8, 10)$ 和 $(5, 15)$。

首先将朋友按金币从小到大排序：$[10, 20]$；房子按价格从小到大排序：$[(10, 8), (15, 5)]$。

• 处理金币为 $10$ 的朋友：价格 $\le 10$ 的房子有第 1 个（舒适度 $8$），购买后获得舒适度 $8$。
• 处理金币为 $20$ 的朋友：价格 $\le 20$ 的房子有第 2 个（舒适度 $5$），购买后舒适度总和增加 $5$。

最终最大舒适度总和为 $8 + 5 = 13$。

样例2

输入

1 2
5
100 10
200 20

输出

0

说明

只有 1 位朋友，金币数为 5；有 2 个房子，舒适度和价格分别为 $(100, 10)$ 和 $(200, 20)$。

朋友的金币为 $5$，而所有房子的价格均大于 $5$，因此该朋友无法购买任何房子。最大舒适度总和为 $0$。

样例3

输入

3 2
100 200 300
40 50
60 150

输出

100

说明

3 位朋友的金币分别为 100, 200, 300；2 个房子信息为：舒适度 $40$ 价格 $50$，舒适度 $60$ 价格 $150$。

朋友按金币排序：$[100, 200, 300]$；房子按价格排序：$[(50, 40), (150, 60)]$。

• 第一位朋友金币 $100$，可买价格 $\le 100$ 的房子：舒适度 $40$ 的一个，购买后总和为 $40$。
• 第二位朋友金币 $200$，可买剩余房子中价格 $\le 200$ 的：舒适度 $60$ 的房子，购买后总和变为 $40 + 60 = 100$。
• 第三位朋友金币 $300$，此时已无剩余房子可买。

最终最大总和为 $100$。