分数: 400 分
问题陈述
高桥的爱好是拍摄山脉照片。
高桥面前,有 N 山脉排成一排,编号从 1 to N.
的 树的 i第一座山的海拔为 A_i 和一个美丽的 B_i.
当云在高处水平扩展时 X,仅具有海拔的山脉 X 或更高(即山脉 i 满意 A_i \geq X)出现在云层上方并且高桥可见。
高桥将可见的山脉数字集划分为连续数字的最大间隔(连续间隔,不能在两端进一步扩展),并将每个间隔拍摄为 山脉.
每一座山脉,最大的美丽 B_i 该范围内的山脉被定义为 查看值 那个山脉的 。
所有山脉的视野值之和称为 总观看价值 在云高度 X.
例如,如果可见的山脉编号是 2, 3, 4, 7, 8,那么有 2 山脉: \{2, 3, 4\} 和 \{7, 8\}.
总观看价值为 \max(B_2, B_3, B_4) + \max(B_7, B_8).
如果看不到山脉,则总视图值为 0.
你被给予 Q 查询。
在 j-th 查询,您将获得云高度 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
- 第一行包含 N,山脉数量,以及 Q,查询数量,以空格分隔。
- 以下 N 行各包含, i第线,海拔 A_i 和美丽 B_i 的 i第一座山,相隔一个空格。
- 以下 Q 行各包含, j第线,云高 X_j 为 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