CSP1262. 全自动灌溉系统（water）

• 时限: 1000 ms | 内存: 512 MB | 难度: 9

全自动灌溉系统

题目描述

由于小 Z 养了一款很名贵的花，需要每时每刻给其浇水，一旦不浇水就会枯萎，因此小 Z 研发了一款全自动灌溉系统。

全自动灌溉系统有 $n$ 个储水箱，第 $i$ 个储水箱的容量是 $a_i$。灌溉系统每时刻可以任意选择一个储水箱，从中抽出 1 单位的水来给花进行灌溉。最初所有储水箱都是满的，之后 $m$ 个时间点，小 Z 在 $t_j$ 的时间回家给第 $x_j$ 个储水箱加满水。同一单位时间，浇水会在小 Z 加水之前。

小 Z 希望他的花能活的尽可能的久，请你帮助他设计灌溉系统的程序使得花能活的尽可能的久。

输入格式

从 water.in 文件读入数据。

输入包含多个测试用例。

第一行包含一个整数 $T$ （$1 \leq T \leq 10^4$），表示测试用例的个数。

对于每个测试用例；

• 第一行包含两个整数 $n$ 和 $m$ ，分别表示储水箱数量和小 Z 回家次数。

• 第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ，表示每个储水箱的容量。

• 接下来的 $m$ 行，每行包含两个整数 $t_j$ 和 $x_j$ ，表示小 Z 在 $t_j$ 的时间回家给第 $x_j$ 个储水箱加满水。

输出格式

输出到 water.out 文件。

对于每个测试用例，输出一行一个整数，表示花能活的最长时间。

样例 #1

样例输入 #1

2
3 1
3 3 3
8 1
2 2
5 2
1 2
2 1

Copy

样例输出 #1

12
9

Copy

提示

【样例 1 解释】

第一组测试用例，先使用第一个水箱浇水再使用第二三个水箱，当小 Z 第 8 秒回家的时候第一个水箱是空的，可以为其补满，所以可以持续浇花到第 12 秒。

第二组测试用例，第一秒先使用第二个水箱浇水，当小 Z 第一次回家时为第二个水箱加满水，这时第二个水箱里还有 1 单位的水，所以小 Z 只加了 1 单位的水。第二秒使用第一个水箱加水，当小 Z 回来的时候，第二个水箱有 4 单位的水，小 Z 向其加了 1 单位的水。所以不难得到可以持续浇花到第 9 秒。可以证明这是最优策略。

样例 2～ 4 都可以点击链接 water_sample.zip 下载大样例压缩包，具体如下。

【样例 2】

见附件的 water_sample2.in 与 water_sample2.ans。

【样例 3】

见附件的 water_sample3.in 与 water_sample3.ans。

【样例 4】

见附件的 water_sample4.in 与 water_sample4.ans。

【数据范围】

对于 $20\%$ 的测试数据，保证 $1\le n \le 2,1\le m\le 10$；

对于 $50\%$ 的测试数据，保证 $1\le n,m \le 2\times10^3$；

另有 $10\%$ 的测试数据，保证 $1\le m \le 2$；

对于 $100\%$ 的测试数据，保证 $1\le n\le 2\times10^5,\ 0\le m\le 2\times10^5，1\le a_i\le10^9,1\le x_i\le n,1\le t_i\le10^9$。并保证所有测试用例中 $n$ 的总和与 $m$ 的总和均不超过 $2\times10^5$。