D - View of the Mountain Range Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は山の写真を撮るのが趣味です。

高橋君の前には N 個の山が一列に並んでおり、山には 1 から N までの番号がついています。

i 番目の山の標高は A_i 、美しさは B_i です。

雲が高さ X で水平に広がっているとき、標高が X 以上である山（すなわち A_i \geq X を満たす山 i）だけが雲の上に顔を出し、高橋君から見えます。

高橋君は、見えている山の番号の集合を、番号が連続している極大な区間（これ以上両端を広げられない連続区間）に分割し、各区間を山脈として撮影します。

各山脈について、その山脈に含まれる山の美しさ B_i の最大値をその山脈の眺望値とします。

すべての山脈の眺望値の合計を、雲の高さ X における眺望値の総和と呼びます。

例えば、見えている山の番号が 2, 3, 4, 7, 8 である場合、山脈は \{2, 3, 4\} と \{7, 8\} の 2 つです。

眺望値の総和は \max(B_2, B_3, B_4) + \max(B_7, B_8) となります。

見えている山がひとつもない場合、眺望値の総和は 0 とします。

Q 個の質問が与えられます。

j 番目の質問では雲の高さ X_j が与えられるので、そのときの眺望値の総和を求めてください。

制約

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

入力

N Q
A_1 B_1
A_2 B_2
\vdots
A_N B_N
X_1
X_2
\vdots
X_Q
  • 1 行目には、山の個数を表す N と、質問の個数を表す Q が、スペース区切りで与えられる。
  • 続く N 行のうち i 行目には、i 番目の山の標高を表す A_i と、美しさを表す B_i が、スペース区切りで与えられる。
  • 続く Q 行のうち j 行目には、j 番目の質問における雲の高さを表す X_j が与えられる。

出力

Q 行出力せよ。

j 行目には、雲の高さが X_j のときの眺望値の総和を出力せよ。

入力例 1

8 4
1 3
5 10
6 2
5 7
2 100
1 6
7 4
7 9
5
7
1
8

出力例 1

19
9
100
0

入力例 2

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

出力例 2

5
13
15
10
0
13

入力例 3

15 8
10 5
4 20
8 15
6 30
3 25
9 10
9 40
2 35
7 12
5 50
11 8
1 45
6 18
10 22
4 28
6
9
1
12
5
10
3
8

出力例 3

117
75
50
0
147
35
118
90

入力例 4

40 15
1 1000000000
1000000000 1
500000000 700
750000000 900
250000000 800
600000000 1200
600000000 1100
100 5000
999999999 300
400000000 400
800000000 2000
200000000 50
300000000 60
700000000 70
700000001 80
123456789 90
987654321 100
111111111 110
222222222 220
333333333 330
444444444 440
555555555 550
666666666 660
777777777 770
888888888 880
999999998 990
135791357 135
246802468 246
357913579 357
468024680 468
579135791 579
680246802 680
791357913 791
802468024 802
913579135 913
24 24
42 42
314159265 314
271828182 271
161803398 161
1
100
1000000000
999999999
800000000
700000000
600000000
500000000
400000000
300000000
200000000
123456789
50
100000001
900000000

出力例 4

1000000000
5314
1
301
4304
5284
6484
6483
6183
6497
5517
4504
5314
3514
2304

入力例 5

1 1
1 1000000000
1000000000

出力例 5

0

Score : 400 pts

Problem Statement

Takahashi's hobby is taking photographs of mountains.

In front of Takahashi, there are N mountains lined up in a row, numbered from 1 to N.

The i-th mountain has an elevation of A_i and a beauty of B_i.

When clouds spread horizontally at height X, only mountains with elevation X or higher (i.e., mountains i satisfying A_i \geq X) appear above the clouds and are visible to Takahashi.

Takahashi divides the set of visible mountain numbers into maximal intervals of consecutive numbers (contiguous intervals that cannot be extended further on either end), and photographs each interval as a mountain range.

For each mountain range, the maximum beauty B_i among the mountains in that range is defined as the view value of that mountain range.

The sum of the view values of all mountain ranges is called the total view value at cloud height X.

For example, if the visible mountain numbers are 2, 3, 4, 7, 8, then there are 2 mountain ranges: \{2, 3, 4\} and \{7, 8\}.

The total view value is \max(B_2, B_3, B_4) + \max(B_7, B_8).

If no mountains are visible, the total view value is 0.

You are given Q queries.

In the j-th query, you are given the cloud height X_j. Determine the total view value at that time.

Constraints

  • 1 \leq N
  • 1 \leq Q
  • N + Q \leq 2 \times 10^5
  • 1 \leq A_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq B_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq X_j \leq 10^9 (1 \leq j \leq Q)
  • All inputs are integers

Input

N Q
A_1 B_1
A_2 B_2
\vdots
A_N B_N
X_1
X_2
\vdots
X_Q
  • The first line contains N, the number of mountains, and Q, the number of queries, separated by a space.
  • The following N lines each contain, on the i-th line, the elevation A_i and beauty B_i of the i-th mountain, separated by a space.
  • The following Q lines each contain, on the j-th line, the cloud height X_j for the j-th query.

Output

Output Q lines.

On the j-th line, output the total view value when the cloud height is X_j.

Sample Input 1

8 4
1 3
5 10
6 2
5 7
2 100
1 6
7 4
7 9
5
7
1
8

Sample Output 1

19
9
100
0

Sample Input 2

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

Sample Output 2

5
13
15
10
0
13

Sample Input 3

15 8
10 5
4 20
8 15
6 30
3 25
9 10
9 40
2 35
7 12
5 50
11 8
1 45
6 18
10 22
4 28
6
9
1
12
5
10
3
8

Sample Output 3

117
75
50
0
147
35
118
90

Sample Input 4

40 15
1 1000000000
1000000000 1
500000000 700
750000000 900
250000000 800
600000000 1200
600000000 1100
100 5000
999999999 300
400000000 400
800000000 2000
200000000 50
300000000 60
700000000 70
700000001 80
123456789 90
987654321 100
111111111 110
222222222 220
333333333 330
444444444 440
555555555 550
666666666 660
777777777 770
888888888 880
999999998 990
135791357 135
246802468 246
357913579 357
468024680 468
579135791 579
680246802 680
791357913 791
802468024 802
913579135 913
24 24
42 42
314159265 314
271828182 271
161803398 161
1
100
1000000000
999999999
800000000
700000000
600000000
500000000
400000000
300000000
200000000
123456789
50
100000001
900000000

Sample Output 4

1000000000
5314
1
301
4304
5284
6484
6483
6183
6497
5517
4504
5314
3514
2304

Sample Input 5

1 1
1 1000000000
1000000000

Sample Output 5

0