校园书展准备展出 n 本图书，第 i 本图书的展示价值为 a_i。
书展还收到了 m 批捐赠图书。第 i 批捐赠中，最多有 b_i 本图书可用于替换，每本的展示价值均为 c_i。
对于每一批捐赠，工作人员可以选择至多 b_i 本当前正在展出的图书，将它们分别替换成该批捐赠图书。可以少替换，也可以一本都不替换。同一本展位上的图书可以在不同批次中被多次替换。
所有操作结束后，展区中仍然恰好有 n 本图书。请你求出它们的展示价值总和的最大值。
第一行输入两个整数 n,m。
第二行输入 n 个整数 a_1,a_2,\ldots,a_n。
接下来 m 行，第 i 行输入两个整数 b_i,c_i。
输出一行一个整数，表示操作结束后的最大展示价值总和。
4 3 6 2 9 4 2 5 1 10 4 3
30
7 4 12 1 8 20 3 15 6 3 10 2 25 5 7 1 100
207
12 6 5 40 12 7 33 18 2 60 21 9 45 16 4 20 7 35 3 100 12 8 5 50 2 70
795
可以先用价值为 5 的图书替换原来价值为 2 的图书，再用价值为 10 的图书替换原来价值为 4 的图书。
最终四本图书的价值为 6,5,9,10，总和为 30。最后一批图书价值只有 3，不进行替换更优。
一次操作允许替换“至多”指定数量的图书，不必把额度全部用完。
对于所有测试数据，保证：
本题共 20 个测试点，每个测试点 5 分。
| 测试点编号 | n\le | m\le | 特殊性质 |
|---|---|---|---|
| 1\sim4 | 200 | 200 | 无 |
| 5\sim6 | 10^3 | 10^3 | 无 |
| 7\sim9 | 10^5 | 10^5 | A |
| 10\sim12 | 10^5 | 10^5 | B |
| 13 | 5000 | 5000 | 无 |
| 14 | 10^4 | 10^4 | 无 |
| 15 | 3\times10^4 | 3\times10^4 | 无 |
| 16 | 5\times10^4 | 5\times10^4 | 无 |
| 17\sim20 | 10^5 | 10^5 | 无 |
特殊性质 A：对于所有 i，均有 c_i\le\min(a_1,a_2,\ldots,a_n)。
特殊性质 B：对于所有 i，均有 b_i=n。