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