题解

贪心

对于每个房子按照舒适度排序从大到小排序，对于其价格 $x$ ，找到所有人中持有的金币第一个 $\ge x$ 的(用二分实现)，表示最适合买当前房子的人，并将其删去即可。

在cpp中动态删除和二分的过程可以用 multiset 来实现

整体时间复杂度: $O(n \log n)$

题目描述

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

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

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

接下来一行 $n$ 个数，第 $i$ 个整数 $x$ 表示第 $i$ 个人的金币 $x$ ， $1 \leq x \leq 10^9$

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

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