分数: 200 点
问题陈述
高桥喜欢胡椒。
一家餐厅有 M 辣椒的类型,称为类型 1,2,\dots,M。有 C_j 克型 j (1 \le j \le M)这家餐厅的胡椒粉。
他命令 N 这家餐厅的菜肴。
由于兼容性,仅键入 A_i 盘子上可以撒胡椒粉 i (1 \le i \le N),以及可撒在菜肴上的辣椒量的上限 i is B_i 克。
另外,他只能使用餐厅提供的胡椒。即类型总量 j 胡椒粉撒不能超过 C_j 克。
他决定在每道菜上撒多少胡椒粉,以最大限度地增加在菜肴上撒的胡椒粉总量。
他总共可以在菜肴上撒多少克辣椒?
约束
- 所有输入值均为整数。
- 1 \le N,M \le 1000
- 1 \le A_i \le M
- 1 \le B_i,C_i \le 10^6
输入
输入由标准输入按以下格式给出:
N M C_1 C_2 \dots C_M A_1 B_1 A_2 B_2 \vdots A_N B_N
输出
将答案输出为整数。
示例输入 1
7 5 4 4 8 3 7 1 2 2 3 5 2 4 10 2 3 5 4 2 3
示例输出 1
15
在此输入中,有五种辣椒,其中 4,4,8,3,7 克型 1,2,3,4,5 胡椒分别。
下面总共给出了 15 克辣椒撒在菜肴上,这是可达到的最大值。
- 洒 2 克型 1 盘子上的胡椒 1.
- 盘子上不要撒胡椒粉 2.
- 洒 2 克型 5 盘子上的胡椒 3.
- 洒 3 克型 4 盘子上的胡椒 4.
- 洒 1 克类型 至少 2 盘子上的胡椒 5.
- 洒 4 克型 5 盘子上的胡椒 6.
- 洒 3 克型 2 盘子上的胡椒 7.
示例输入 2
1 1 1 1 1
示例输出 2
1
示例输入 3
15 10 7 94 100 82 63 81 75 2 76 73 10 44 5 77 10 47 7 32 2 82 5 90 3 37 6 70 6 28 3 25 2 26 10 56 1 69 5 46 7 26
示例输出 3
438