题目描述

有 $N$ 位偶像：偶像 $1,2,\dots,N$。有 $M$ 首候选歌曲，编号为 歌曲 $1,2,\dots,M$。 制作人先生想从这些歌曲中选择若干首（可以为 $0$ 首）来举办演出，但同一首歌最多只能被选一次。

• 偶像 $i$（$1\le i\le N$）最多可以跳 $A_i$ 首歌。
• 若在演出中选了歌曲 $j$（$1\le j\le M$），则该首歌需要 $B_j$ 位偶像来跳，并且无论由谁来跳，该首歌带来的兴奋值为 $C_j$。

制作人先生在满足每位偶像跳歌次数均不超过自身上限 $A_i$ 的前提下，选择若干首歌曲并为每首已选的歌曲分配跳舞的偶像，求能够获得的最大总兴奋值（已选歌曲的 $C_j$ 之和）。

输入格式

输入共 $M+2$ 行；

• 第一行两个由空格隔开的整数 $N,M$；
• 第二行 $N$ 个由空格隔开的整数，第 $i$（$1 \le i \le N$） 个整数代表 $A_i$；
• 后面 $M$ 行每行两个由空格隔开的整数，第 $j$ （$1 \le j \le M$）行的两个整数代表 $B_j, C_j$。

输出格式

输出一个整数，表示 制作人先生 所能获得的最大总兴奋值。

样例输入 1

3 3
1 1 3
1 1
2 5
3 10

样例输出 1

11

样例输入 2

2 6
6 0
0 1000000000
0 1000000000
1 1000000000
1 1000000000
1 1000000000
2 1000000000

样例输出 2

5000000000

说明

样例 1 解释

可以选择歌曲 $1,3$，并安排如下：

• 歌曲 $1$：仅偶像 $3$ 跳；
• 歌曲 $3$：偶像 $1,2,3$ 都跳。 此时三位偶像跳歌次数分别为 $1,1,2$，均不超过各自上限，获得的总兴奋值为 $1+10=11$，无法再得到更大值。

样例 2 解释

可以选择歌曲 $1,2,3,4,5$ 并安排：

• 歌曲 $1,2$：不需要人跳；
• 歌曲 $3,4,5$：均由偶像 $1$ 单独跳。 总兴奋值为 $5\times 10^9$，这是最大可能值。

数据范围

• $1\le N\le 100$
• $1\le M\le 100$
• $0\le A_i\le M$
• $0\le B_j\le N$
• $0\le C_j\le 10^9$
• 所有输入值均为整数。