解题思路

将朋友按金币数从小到大排序，房子按价格从小到大排序。

依次处理每个朋友：

• 把当前朋友能买得起的所有房子加入最大堆，堆中按舒适度排序。
• 当前朋友选择堆中舒适度最大的房子购买。
• 该房子被购买后从堆中删除。

题目内容

小强有 $n$ 个朋友，每个朋友有一定数量的金币，现在他们要购买房子，一共有 $m$ 个房子，每个房子有两个参数：舒适度和价格，当一个人的金币大于等于一个房子的价格时，才可以购买房子，且要满足以下条件：

1. 一个人至多购买一个房子。

2. 一个房子至多被一个人购买。

现在小强想知道 $n$ 个朋友购买的房子的舒适度之和最大可能是多少？

输入描述

第一行两个整数 $n,m$

接下来一行 $n$ 个数，第 $i_{th}$ 个整数 $x$ 表示第 $i$ 个人的金币 $x, 1 \le x \le 10^9$

接下来 $m$ 行每行两个整数表示每个房子的舒适度 $a$ 和价格 $b, 1 \le a,b \le 10^9 1 \le n,m \le 2 * 10^5$

输出描述

输出一个数表示最大可能的舒适度之和

样例1

输入

2 2
2 2
2 2
2 2

输出

2

说明

每个朋友都会买一个舒适度为 $2$ 的房子