C - Observatory with a Mountain View Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は登山が趣味で、各地の展望台から見える山々の情報をまとめています。

ある山岳地帯には N 座の山があり、 i 番目の山は標高 Y_i メートル、その山の美しさの評価値は P_i です。

高橋君は Q 回の調査を行います。各調査では、基準となる標高 L_j が決められており、標高が L_j 以上であるすべての山の美しさの評価値の合計を求めたいと考えています。

各調査に対する答えを求めてください。

制約

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq Y_i \leq 10^9
  • 1 \leq P_i \leq 10^9
  • 1 \leq L_j \leq 10^9
  • 入力はすべて整数である

入力

N Q
Y_1 P_1
Y_2 P_2
:
Y_N P_N
L_1
L_2
:
L_Q
  • 1 行目には、山の数を表す N 、調査の回数を表す Q が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各山の情報が与えられる。
  • 1 + i 行目では、 i 番目の山の標高 Y_i と美しさの評価値 P_i が、スペース区切りで与えられる。
  • N + 2 行目から N + 1 + Q 行目では、各調査の基準標高が与えられる。
  • N + 1 + j 行目では、 j 番目の調査の基準標高 L_j が与えられる。

出力

Q 行にわたって、各調査の答えを出力せよ。 j 行目には、 j 番目の調査に対して、標高が L_j 以上であるすべての山の美しさの評価値の合計を出力せよ。該当する山が存在しない場合は 0 を出力せよ。

入力例 1

3 2
100 5
200 10
300 15
150
100

出力例 1

25
30

入力例 2

3 3
100 3
200 7
300 11
500
300
1

出力例 2

0
11
21

入力例 3

8 5
50 2
120 8
300 15
500 20
700 25
1000 30
1500 50
2000 100
600
1000
2000
2001
1

出力例 3

205
180
100
0
250

入力例 4

15 10
80 12
150 25
300 18
450 30
600 45
800 55
1200 60
1800 70
2500 85
3000 100
4000 120
5500 200
7000 150
8500 300
10000 500
1
500
1000
2000
3000
5000
7000
9000
10000
10001

出力例 4

1770
1685
1585
1455
1370
1150
950
500
500
0

入力例 5

1 1
1000000000 1000000000
1000000000

出力例 5

1000000000

Score : 366 pts

Problem Statement

Takahashi's hobby is mountain climbing, and he is compiling information about the mountains visible from observatories in various locations.

In a certain mountainous region, there are N mountains. The i-th mountain has an elevation of Y_i meters and a beauty rating of P_i.

Takahashi conducts Q surveys. In each survey, a reference elevation L_j is specified, and he wants to find the total beauty rating of all mountains whose elevation is at least L_j.

Find the answer for each survey.

Constraints

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq Y_i \leq 10^9
  • 1 \leq P_i \leq 10^9
  • 1 \leq L_j \leq 10^9
  • All input values are integers

Input

N Q
Y_1 P_1
Y_2 P_2
:
Y_N P_N
L_1
L_2
:
L_Q
  • The first line contains N, the number of mountains, and Q, the number of surveys, separated by a space.
  • From the 2nd line to the (N + 1)-th line, information about each mountain is given.
  • The (1 + i)-th line contains the elevation Y_i and the beauty rating P_i of the i-th mountain, separated by a space.
  • From the (N + 2)-th line to the (N + 1 + Q)-th line, the reference elevation for each survey is given.
  • The (N + 1 + j)-th line contains the reference elevation L_j for the j-th survey.

Output

Output Q lines, each containing the answer to the corresponding survey. On the j-th line, output the total beauty rating of all mountains whose elevation is at least L_j. If no such mountain exists, output 0.

Sample Input 1

3 2
100 5
200 10
300 15
150
100

Sample Output 1

25
30

Sample Input 2

3 3
100 3
200 7
300 11
500
300
1

Sample Output 2

0
11
21

Sample Input 3

8 5
50 2
120 8
300 15
500 20
700 25
1000 30
1500 50
2000 100
600
1000
2000
2001
1

Sample Output 3

205
180
100
0
250

Sample Input 4

15 10
80 12
150 25
300 18
450 30
600 45
800 55
1200 60
1800 70
2500 85
3000 100
4000 120
5500 200
7000 150
8500 300
10000 500
1
500
1000
2000
3000
5000
7000
9000
10000
10001

Sample Output 4

1770
1685
1585
1455
1370
1150
950
500
500
0

Sample Input 5

1 1
1000000000 1000000000
1000000000

Sample Output 5

1000000000