AT_abc424_g [ABC424G] Set list

有 $N$ 位偶像：偶像 $1$、偶像 $2$、$\ldots$、偶像 $N$。 有 $M$ 首候选歌曲，编号为歌曲 $1$、歌曲 $2$、$\ldots$、歌曲 $M$。 高桥想从这些歌曲中选择若干首（可以为 $0$ 首），举办一场现场演出。 但是，每首歌曲最多只能被选择一次。 偶像 $i$（$1\leq i\leq N$）最多能跳 $A_i$ 首歌。 在现场演出中，歌曲 $j$（$1\leq j\leq M$）需要 $B_j$ 位偶像跳舞，无论谁跳舞，这首歌的兴奋度都是 $C_j$。 高桥会选择要表演的歌曲，并为每首被选中的歌曲分配要跳舞的偶像，使得每位偶像跳舞的总次数不超过各自允许的次数。请你求出在满足条件的情况下，所能获得的最大兴奋度和。

输入通过标准输入给出，格式如下： > $N$ $M$ > $A_1$ $A_2$ $\ldots$ $A_N$ > $B_1$ $C_1$ > $B_2$ $C_2$ > $\vdots$ > $B_M$ $C_M$

输出高桥能够获得的歌曲兴奋度之和的最大值。

### 样例解释 1 例如，他可以选择歌曲 $1,3$，并将跳舞的偶像分配如下： - 在歌曲 $1$ 中，只有偶像 $3$ 跳舞。 - 在歌曲 $3$ 中，偶像 $1,2,3$ 跳舞。 此时，偶像 $1,2,3$ 的跳舞次数分别为 $1,1,2$，均满足条件。此时获得的兴奋度和为 $1+10=11$。 无法在满足条件的情况下获得更大的兴奋度和，所以输出 $11$。 ### 样例解释 2 例如，他可以选择歌曲 $1,2,3,4,5$，并将跳舞的偶像分配如下： - 在歌曲 $1$ 中，没有偶像跳舞。 - 在歌曲 $2$ 中，没有偶像跳舞。 - 在歌曲 $3$ 中，只有偶像 $1$ 跳舞。 - 在歌曲 $4$ 中，只有偶像 $1$ 跳舞。 - 在歌曲 $5$ 中，只有偶像 $1$ 跳舞。 此时兴奋度和为 $5000000000$，并且这是最大值。 ### 数据范围 - $1\leq N\leq 100$ - $1\leq M\leq 100$ - $0\leq A_i\leq M$ - $0\leq B_i\leq N$ - $0\leq C_i\leq 10^9$ - 输入的所有数均为整数。 由 ChatGPT 5 翻译