#P1848. 2024.7.27-KDXF-第一题-购房之旅

2024.7.27-KDXF-第一题-购房之旅

题目描述

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

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

现在塔子哥想知道 nn 个朋友购买的房子的舒适度之和最大可能是多少？

输入描述

第一行两个整数 nn 和 mm

接下来一行 nn 个数，第 ii 个整数 xx 表示第 ii 个人的金币 xx， 1≤x≤1091 \leq x \leq 10^9

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

输出描述

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

示例 1

输入

2 2
2 2 
2 2
2 2

输出

4

知识点:*****

查看知识点以及同类型题目

Statistics