分数: 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