B - Pepper Addiction Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 200 点

問題文

高橋君はコショウが大好きです。

M 種類のコショウがレストランに置いてあり、それぞれを種類 1,2,\dots,M と呼びます。　このレストランに種類 j ( 1 \le j \le M ) のコショウは C_j g だけあります。

高橋君はこの店で N 個の料理を注文しました。
相性の都合で i ( 1 \le i \le N ) 番目の料理には種類 A_i のコショウしかかけることができず、 i 番目の料理にかけられるコショウの量の上限は B_i g です。
また、高橋君がこれらの料理にかけられるのはレストランに置いてあるコショウのみです。つまり、種類 j のコショウを合計 C_j g を超えてかけることはできません。

高橋君は、料理にかけたコショウの量の合計を最大にするようにどの料理にどれだけのコショウをかけるかを決めます。
このとき、高橋君は合計何 g のコショウを料理にかけることができますか？

制約

  • 入力は全て整数
  • 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

この入力では 5 種類のコショウがあり、種類 1,2,3,4,5 のコショウがそれぞれ 4,4,8,3,7 g あります。
以下のようにすると料理にかけたコショウの量の合計が 15 g となり、これが達成可能な最大です。

  • 1 番目の料理に種類 1 のコショウを 2 g かける。
  • 2 番目の料理にはコショウをかけない。
  • 3 番目の料理に種類 5 のコショウを 2 g かける。
  • 4 番目の料理に種類 4 のコショウを 3 g かける。
  • 5 番目の料理に種類 2 のコショウを 1 g かける。
  • 6 番目の料理に種類 5 のコショウを 4 g かける。
  • 7 番目の料理に種類 2 のコショウを 3 g かける。

入力例 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

Score : 200 points

Problem Statement

Takahashi loves pepper.

A restaurant has M types of pepper, called type 1,2,\dots,M. There are C_j grams of type j (1 \le j \le M) pepper at this restaurant.

He ordered N dishes at this restaurant.
Due to compatibility, only type A_i pepper can be sprinkled on dish i (1 \le i \le N), and the upper limit on the amount of pepper that can be sprinkled on dish i is B_i grams.
Also, he can only use the pepper available at the restaurant. That is, the total amount of type j pepper sprinkled cannot exceed C_j grams.

He decides how much pepper to sprinkle on each dish to maximize the total amount of pepper sprinkled on the dishes.
How many grams of pepper in total can he sprinkle on the dishes?

Constraints

  • All input values are integers.
  • 1 \le N,M \le 1000
  • 1 \le A_i \le M
  • 1 \le B_i,C_i \le 10^6

Input

The input is given from Standard Input in the following format:

N M
C_1 C_2 \dots C_M
A_1 B_1
A_2 B_2
\vdots
A_N B_N

Output

Output the answer as an integer.

Sample Input 1

7 5
4 4 8 3 7
1 2
2 3
5 2
4 10
2 3
5 4
2 3

Sample Output 1

15

In this input, there are five types of pepper, with 4,4,8,3,7 grams of type 1,2,3,4,5 pepper respectively.
The following gives a total of 15 grams of pepper sprinkled on the dishes, which is the maximum achievable.

  • Sprinkle 2 grams of type 1 pepper on dish 1.
  • Sprinkle no pepper on dish 2.
  • Sprinkle 2 grams of type 5 pepper on dish 3.
  • Sprinkle 3 grams of type 4 pepper on dish 4.
  • Sprinkle 1 gram of type 2 pepper on dish 5.
  • Sprinkle 4 grams of type 5 pepper on dish 6.
  • Sprinkle 3 grams of type 2 pepper on dish 7.

Sample Input 2

1 1
1
1 1

Sample Output 2

1

Sample Input 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

Sample Output 3

438