AT_abc448_b [ABC448B] Pepper Addiction

高桥非常喜欢胡椒。 一家餐厅有 $M$ 种胡椒，分别编号为 $1,2,\dots,M$。第 $j$ 种胡椒有 $C_j$ 克（$1 \le j \le M$）。 他在餐厅点了 $N$ 道菜。 由于相容性问题，第 $i$ 道菜只能撒第 $A_i$ 种胡椒（$1 \le i \le N$），并且每道菜最多能撒 $B_i$ 克胡椒。 此外，他只能使用餐厅现有的胡椒，也就是说，每种第 $j$ 种胡椒撒到所有菜上的总量不能超过 $C_j$ 克。 他要决定每道菜要撒多少克胡椒，以使撒在所有菜上的胡椒总量最大。 请问他最多能在菜上撒多少克胡椒？

输入按如下格式从标准输入读入： > $N$ $M$ > $C_1$ $C_2$ $\dots$ $C_M$ > $A_1$ $B_1$ > $A_2$ $B_2$ > $\vdots$ > $A_N$ $B_N$

输出一个整数，表示最多能撒在菜上的胡椒总克数。

### 样例解释 1 本输入数据中，有五种胡椒，每种分别有 $4,4,8,3,7$ 克，第 $1,2,3,4,5$ 种胡椒分别有 $4,4,8,3,7$ 克。 按照如下分配，可以让总共撒在菜上的胡椒达到最大 $15$ 克： - 第 1 道菜撒 2 克第 1 种胡椒。 - 第 2 道菜不撒胡椒。 - 第 3 道菜撒 2 克第 5 种胡椒。 - 第 4 道菜撒 3 克第 4 种胡椒。 - 第 5 道菜撒 1 克第 2 种胡椒。 - 第 6 道菜撒 4 克第 5 种胡椒。 - 第 7 道菜撒 3 克第 2 种胡椒。 ### 数据范围 - 所有输入值均为整数。 - $1 \le N, M \le 1000$ - $1 \le A_i \le M$ - $1 \le B_i, C_i \le 10^6$ 由 ChatGPT 5 翻译