← 返回题目列表

AtCoder · awc0032_c

C. 山景展望台

中文机器翻译题面 查看原题

分数: 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
  • 第一行包含 N,山脉数量,以及 Q,调查数量,以空格分隔。
  • 从第 2 行到 (N + 1)第行,给出了每座山的信息。
  • 的 (1 + i)第行包含海拔 Y_i 和美丽评级 P_i 的 i第一座山,相隔一个空格。
  • 从 (N + 2)第 行 (N + 1 + Q)第行,给出了每次测量的参考高程。
  • 的 (N + 1 + j)第行包含参考高程 L_j 为 j第次调查。

输出

输出 Q 行,每行包含相应调查的答案。上 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