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 翻译