D - Package Assignment at the Distribution Center Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は配送センターの管理者です。この配送センターには N 台のトラックがあり、今日届いた M 個の荷物のうち、できるだけ多くの荷物をトラックに積み込んで配送したいと考えています。

荷物 j（1 \leq j \leq M）の重量は D_j です。

トラック i（1 \leq i \leq N）には、荷物 1 個あたりの重量上限 E_i と、積載可能な荷物の個数上限 C_i が定められています。トラック i には、重量が E_i 以下の荷物（すなわち D_j \leq E_i を満たす荷物 j）のみを積み込むことができ、積み込める荷物の個数は最大 C_i 個です。この重量の条件は荷物ごとに個別に判定されます。すなわち、1 台のトラックに複数の荷物を積む場合でも、個々の荷物の重量がそれぞれ E_i 以下であればよく、積み込んだ荷物の合計重量に関する制約はありません。

各荷物はトラックに積み込む場合、ちょうど 1 台のトラックに積み込みます。同じ荷物を複数のトラックに積み込むことはできません。また、すべての荷物を配送する必要はなく、どのトラックにも積み込まない荷物があっても構いません。

配送できる荷物の最大個数を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq E_i \leq 10^9
  • 1 \leq C_i \leq M
  • 1 \leq D_j \leq 10^9
  • 入力はすべて整数である。

入力

N M
E_1 C_1
E_2 C_2
\vdots
E_N C_N
D_1 D_2 \ldots D_M
  • 1 行目には、トラックの台数を表す N と、荷物の個数を表す M が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各トラックの情報が与えられる。
  • 1 + i 行目（1 \leq i \leq N）では、トラック i の荷物 1 個あたりの重量上限 E_i と、積載可能な荷物の個数上限 C_i が、スペース区切りで与えられる。
  • N + 2 行目では、各荷物の重量 D_1, D_2, \ldots, D_M が、スペース区切りで与えられる。

出力

配送できる荷物の最大個数を 1 行で出力せよ。

入力例 1

3 5
5 2
10 1
3 2
2 4 6 8 11

出力例 1

3

入力例 2

2 4
3 2
5 2
6 7 8 9

出力例 2

0

入力例 3

7 15
4 3
8 2
15 4
10 1
6 5
20 2
12 3
1 5 6 7 8 9 10 11 12 13 14 15 16 20 21

出力例 3

14

入力例 4

20 60
100 3
50 4
200 5
75 2
150 6
30 5
500 4
250 3
10 10
90 2
120 4
60 6
300 5
40 3
180 7
220 2
15 8
80 4
1000 6
130 3
5 12 18 25 33 37 42 48 55 59 63 70 77 83 88 92 99 105 111 119 125 132 140 148 155 163 172 181 190 205 215 230 245 260 275 290 310 330 350 370 390 410 430 450 470 490 510 530 550 570 590 610 700 800 900 1000 1100 1200 1300 1400

出力例 4

46

入力例 5

1 1
1000000000 1
1000000000

出力例 5

1

Score : 400 pts

Problem Statement

Takahashi is the manager of a distribution center. This distribution center has N trucks, and he wants to load and deliver as many packages as possible out of the M packages that arrived today.

The weight of package j (1 \leq j \leq M) is D_j.

For truck i (1 \leq i \leq N), a weight limit per package E_i and a maximum number of packages C_i are specified. Truck i can only load packages whose weight is at most E_i (i.e., packages j satisfying D_j \leq E_i), and the number of packages it can carry is at most C_i. The weight condition is checked individually for each package. That is, even when loading multiple packages onto a single truck, it is sufficient that each individual package's weight is at most E_i; there is no constraint on the total weight of the loaded packages.

Each package, if loaded onto a truck, must be loaded onto exactly one truck. The same package cannot be loaded onto multiple trucks. Also, it is not necessary to deliver all packages; some packages may remain unloaded on any truck.

Find the maximum number of packages that can be delivered.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq E_i \leq 10^9
  • 1 \leq C_i \leq M
  • 1 \leq D_j \leq 10^9
  • All input values are integers.

Input

N M
E_1 C_1
E_2 C_2
\vdots
E_N C_N
D_1 D_2 \ldots D_M
  • The first line contains N, the number of trucks, and M, the number of packages, separated by a space.
  • From the 2nd line to the (N + 1)-th line, the information for each truck is given.
  • The (1 + i)-th line (1 \leq i \leq N) contains the weight limit per package E_i and the maximum number of packages C_i for truck i, separated by a space.
  • The (N + 2)-th line contains the weights of the packages D_1, D_2, \ldots, D_M, separated by spaces.

Output

Output the maximum number of packages that can be delivered, in a single line.

Sample Input 1

3 5
5 2
10 1
3 2
2 4 6 8 11

Sample Output 1

3

Sample Input 2

2 4
3 2
5 2
6 7 8 9

Sample Output 2

0

Sample Input 3

7 15
4 3
8 2
15 4
10 1
6 5
20 2
12 3
1 5 6 7 8 9 10 11 12 13 14 15 16 20 21

Sample Output 3

14

Sample Input 4

20 60
100 3
50 4
200 5
75 2
150 6
30 5
500 4
250 3
10 10
90 2
120 4
60 6
300 5
40 3
180 7
220 2
15 8
80 4
1000 6
130 3
5 12 18 25 33 37 42 48 55 59 63 70 77 83 88 92 99 105 111 119 125 132 140 148 155 163 172 181 190 205 215 230 245 260 275 290 310 330 350 370 390 410 430 450 470 490 510 530 550 570 590 610 700 800 900 1000 1100 1200 1300 1400

Sample Output 4

46

Sample Input 5

1 1
1000000000 1
1000000000

Sample Output 5

1