D - Product Return Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は工場の検品担当者です。ベルトコンベア上に横一列に並んだ N 個の製品を検査しています。

i 番目（1 \leq i \leq N）の製品には品質スコア A_i と重量 B_i が設定されています。

基準値を K としたとき、品質スコアが K 未満（A_i < K）である製品は不良品とみなし、すべて返送する必要があります。品質スコアが K 以上の製品は良品です。

返送する不良品は箱に入れて発送します。各不良品はちょうど 1 つの箱に入れなければならず、箱には不良品のみを入れます。空の箱は使いません。箱の個数は自由に選べますが、それぞれの箱について以下の条件を満たす必要があります。

  • 同じ箱に入れる不良品は、元の並びにおいて連続する区間を成さなければならない。すなわち、ある箱に入れる不良品の位置を l, l+1, \ldots, r（l \leq r）としたとき、l から r までのすべての製品が不良品でなければならない（間に良品が存在してはならない）。

1 つの箱の送料は、その箱に含まれる不良品の重量の最大値で決まります。具体的には、箱に含まれる製品の重量 B_i の最大値がその箱の送料です。送料の合計は、すべての箱の送料の和です。

Q 個の基準値 K_1, K_2, \ldots, K_Q が与えられます。各 K_j について、不良品をすべて返送するための送料の合計の最小値を求めてください。不良品が存在しない場合、送料の合計は 0 です。

各問い合わせは互いに独立です（製品の並びは共通ですが、基準値のみが変わります）。

制約

  • 1 \leq N
  • 1 \leq Q
  • N + Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • 1 \leq K_j \leq 10^9
  • 入力はすべて整数である

入力

N Q
A_1 B_1
A_2 B_2
\vdots
A_N B_N
K_1
K_2
\vdots
K_Q
  • 1 行目には、製品の数を表す N と、問い合わせの数を表す Q が、スペース区切りで与えられる。
  • 2 行目から N+1 行目では、各製品の情報が与えられる。
  • 1 + i 行目には、i 番目の製品の品質スコアを表す A_i と、重量を表す B_i が、スペース区切りで与えられる。
  • 続く Q 行では、基準値が与えられる。
  • N + 1 + j 行目には、j 番目の問い合わせの基準値を表す K_j が与えられる。

出力

Q 行出力してください。

j 行目には、基準値を K_j としたときの送料の合計の最小値を整数で出力してください。

入力例 1

5 4
5 3
2 10
4 2
1 7
6 4
1
3
5
7

出力例 1

0
17
10
10

入力例 2

4 5
3 8
3 2
1 5
4 6
1
2
3
4
5

出力例 2

0
5
5
8
8

入力例 3

12 8
8 5
3 12
10 4
1 7
6 6
2 20
9 3
5 15
4 8
7 10
11 2
3 9
1
4
6
9
12
3
10
5

出力例 3

0
48
63
56
20
27
41
56

入力例 4

30 10
100 30
20 5
80 100
40 7
60 50
10 80
90 20
30 60
70 10
50 90
25 55
75 35
15 75
85 15
35 65
95 25
45 85
55 45
5 95
65 40
12 70
88 22
42 82
78 32
18 72
58 52
98 12
28 62
68 42
38 92
1
11
31
51
71
91
101
46
66
86

出力例 4

0
175
574
940
656
287
100
905
778
459

入力例 5

1 1
1 1000000000
1000000000

出力例 5

1000000000

Score : 400 pts

Problem Statement

Takahashi is a quality inspector at a factory. He is inspecting N products lined up in a row on a belt conveyor.

The i-th product (1 \leq i \leq N) has a quality score A_i and a weight B_i.

Given a threshold value K, any product with a quality score less than K (A_i < K) is considered defective and must be returned. Products with a quality score of K or higher are considered good.

Defective products to be returned are packed into boxes for shipping. Each defective product must be placed in exactly one box, and boxes may only contain defective products. Empty boxes are not used. The number of boxes can be chosen freely, but each box must satisfy the following condition:

  • The defective products placed in the same box must form a contiguous segment in the original arrangement. That is, if the positions of defective products placed in a box are l, l+1, \ldots, r (l \leq r), then all products from position l to r must be defective (no good products may exist in between).

The shipping cost of a single box is determined by the maximum weight among the defective products it contains. Specifically, the maximum value of B_i among the products in the box is the shipping cost of that box. The total shipping cost is the sum of the shipping costs of all boxes.

You are given Q threshold values K_1, K_2, \ldots, K_Q. For each K_j, find the minimum total shipping cost to return all defective products. If there are no defective products, the total shipping cost is 0.

Each query is independent (the arrangement of products is shared, but only the threshold value changes).

Constraints

  • 1 \leq N
  • 1 \leq Q
  • N + Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9
  • 1 \leq B_i \leq 10^9
  • 1 \leq K_j \leq 10^9
  • All input values are integers

Input

N Q
A_1 B_1
A_2 B_2
\vdots
A_N B_N
K_1
K_2
\vdots
K_Q
  • The first line contains N, the number of products, and Q, the number of queries, separated by a space.
  • From the 2nd line to the (N+1)-th line, information about each product is given.
  • The (1 + i)-th line contains A_i, the quality score of the i-th product, and B_i, its weight, separated by a space.
  • The following Q lines give the threshold values.
  • The (N + 1 + j)-th line contains K_j, the threshold value for the j-th query.

Output

Print Q lines.

On the j-th line, print the minimum total shipping cost when the threshold value is K_j, as an integer.

Sample Input 1

5 4
5 3
2 10
4 2
1 7
6 4
1
3
5
7

Sample Output 1

0
17
10
10

Sample Input 2

4 5
3 8
3 2
1 5
4 6
1
2
3
4
5

Sample Output 2

0
5
5
8
8

Sample Input 3

12 8
8 5
3 12
10 4
1 7
6 6
2 20
9 3
5 15
4 8
7 10
11 2
3 9
1
4
6
9
12
3
10
5

Sample Output 3

0
48
63
56
20
27
41
56

Sample Input 4

30 10
100 30
20 5
80 100
40 7
60 50
10 80
90 20
30 60
70 10
50 90
25 55
75 35
15 75
85 15
35 65
95 25
45 85
55 45
5 95
65 40
12 70
88 22
42 82
78 32
18 72
58 52
98 12
28 62
68 42
38 92
1
11
31
51
71
91
101
46
66
86

Sample Output 4

0
175
574
940
656
287
100
905
778
459

Sample Input 5

1 1
1 1000000000
1000000000

Sample Output 5

1000000000