D - Fruit Picking Festival Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は果物狩りフェスティバルに参加しています。フェスティバルの農園には N 本の果樹があり、それぞれの木には果物が 1 つずつ実っています。i 番目の木 (1 \leq i \leq N) の果物のおいしさは V_i で、その果物は高さ D_i の位置に実っています。

高橋君には合計 M 回の収穫チャンスが与えられています。j 回目 (1 \leq j \leq M) の収穫チャンスでは、高さ L_j の脚立が 1 つ割り当てられており、高橋君はこの脚立を使うことで高さ L_j 以下の位置にある果物に手が届きます。

収穫チャンスは j = 1, 2, \ldots, M の順番に 1 回ずつ行われます。各収穫チャンスにおいて、高橋君は以下のいずれか一方を行います。

  • まだ収穫されていない果物のうち、D_i \leq L_j を満たすものを 1 つ選んで収穫する。
  • 何も収穫せずにパスする。

同じ果物を複数回収穫することはできません。すなわち、ある収穫チャンスで収穫された果物は、以降の収穫チャンスでは選べなくなります。

高橋君が M 回の収穫チャンスを通じて収穫できる果物のおいしさの合計の最大値を求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq D_i \leq 10^9
  • 1 \leq V_i \leq 10^9
  • 1 \leq L_j \leq 10^9
  • 入力はすべて整数である

入力

N M
D_1 V_1
D_2 V_2
\vdots
D_N V_N
L_1 L_2 \ldots L_M
  • 1 行目には、果樹の本数を表す整数 N と収穫チャンスの回数を表す整数 M が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各果樹の情報が与えられる。
  • 1 + i 行目には、i 番目の木の果物の高さ D_i とおいしさ V_i が、スペース区切りで与えられる。
  • N + 2 行目には、各収穫チャンスで割り当てられる脚立の高さ L_1, L_2, \ldots, L_M が、スペース区切りで与えられる。

出力

高橋君が収穫できる果物のおいしさの合計の最大値を 1 行で出力せよ。

入力例 1

4 3
2 10
5 30
3 20
1 5
3 2 5

出力例 1

60

入力例 2

3 4
10 100
1 20
2 50
1 1 2 1

出力例 2

70

入力例 3

10 8
8 40
3 100
5 60
10 200
1 15
7 90
4 55
6 70
2 80
9 120
4 6 3 10 5 8 1 7

出力例 3

670

入力例 4

30 25
12 500
3 1000000000
25 450
7 300
18 760
2 50
30 900
15 610
9 400
22 850
5 120
11 530
28 990
14 600
1 10
20 800
6 250
24 870
17 700
10 480
13 560
27 950
4 200
19 780
8 350
21 820
16 650
29 980
23 860
26 930
5 10 15 20 25 30 1 6 12 18 24 30 3 9 14 22 27 2 7 13 19 26 28 4 11

出力例 4

1000014280

入力例 5

1 1
1000000000 1000000000
1

出力例 5

0

Score : 400 pts

Problem Statement

Takahashi is participating in a fruit picking festival. The festival's orchard has N fruit trees, each bearing exactly one fruit. The fruit on the i-th tree (1 \leq i \leq N) has a deliciousness of V_i and grows at height D_i.

Takahashi is given a total of M harvesting chances. In the j-th (1 \leq j \leq M) harvesting chance, he is assigned a stepladder of height L_j, which allows him to reach any fruit at height L_j or below.

The harvesting chances occur one at a time in the order j = 1, 2, \ldots, M. During each harvesting chance, Takahashi performs one of the following:

  • Choose and harvest one fruit that has not yet been harvested and satisfies D_i \leq L_j.
  • Pass without harvesting anything.

The same fruit cannot be harvested more than once. That is, a fruit harvested during one harvesting chance cannot be chosen in any subsequent harvesting chance.

Find the maximum total deliciousness of fruits that Takahashi can harvest over the M harvesting chances.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq M \leq 2 \times 10^5
  • 1 \leq D_i \leq 10^9
  • 1 \leq V_i \leq 10^9
  • 1 \leq L_j \leq 10^9
  • All input values are integers.

Input

N M
D_1 V_1
D_2 V_2
\vdots
D_N V_N
L_1 L_2 \ldots L_M
  • The first line contains an integer N representing the number of fruit trees and an integer M representing the number of harvesting chances, separated by a space.
  • From the 2nd line to the (N + 1)-th line, information about each fruit tree is given.
  • The (1 + i)-th line contains the height D_i and deliciousness V_i of the fruit on the i-th tree, separated by a space.
  • The (N + 2)-th line contains the heights L_1, L_2, \ldots, L_M of the stepladders assigned for each harvesting chance, separated by spaces.

Output

Output in one line the maximum total deliciousness of fruits that Takahashi can harvest.

Sample Input 1

4 3
2 10
5 30
3 20
1 5
3 2 5

Sample Output 1

60

Sample Input 2

3 4
10 100
1 20
2 50
1 1 2 1

Sample Output 2

70

Sample Input 3

10 8
8 40
3 100
5 60
10 200
1 15
7 90
4 55
6 70
2 80
9 120
4 6 3 10 5 8 1 7

Sample Output 3

670

Sample Input 4

30 25
12 500
3 1000000000
25 450
7 300
18 760
2 50
30 900
15 610
9 400
22 850
5 120
11 530
28 990
14 600
1 10
20 800
6 250
24 870
17 700
10 480
13 560
27 950
4 200
19 780
8 350
21 820
16 650
29 980
23 860
26 930
5 10 15 20 25 30 1 6 12 18 24 30 3 9 14 22 27 2 7 13 19 26 28 4 11

Sample Output 4

1000014280

Sample Input 5

1 1
1000000000 1000000000
1

Sample Output 5

0