← 返回题目列表

AtCoder · abc448_b

C. 胡椒成瘾

中文机器翻译题面 查看原题

分数: 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