分数: 466 分
问题陈述
高桥正在一维数轴上散步。最初,高桥处于坐标位置 0.
高桥有 N 运动计划。执行 i-th (1 \leq i \leq N) 计划添加 D_i 到他当前的坐标。 D_i 是一个非零整数;当正值时,他朝正方向移动;当负值时,他朝负方向移动。
有 M 路障放置在数轴上。的 j-th (1 \leq j \leq M) 路障位于坐标处 X_j。执行计划时,高桥会离开当前坐标 s 协调 s + D_i,如果之间至少存在一个路障 s 和 s + D_i (包括两个端点),即如果存在 X_j 满意 \min(s,\, s + D_i) \le X_j \le \max(s,\, s + D_i),然后 碰撞 发生 并且计划无法执行。
高桥按照从 1-st 到 N-th。对于每个计划,如果发生冲突,他必须跳过该计划。如果不会发生碰撞,他可以自由选择执行或跳过该计划。
考虑所有计划后,求高桥的最大可能坐标。
约束
- 1 \leq N \leq 5 \times 10^4
- 0 \leq M \leq 2 \times 10^5
- -5 \times 10^4 \leq D_i \leq 5 \times 10^4
- D_i \neq 0
- \displaystyle \sum_{i=1}^{N} |D_i| \leq 5 \times 10^4
- -10^9 \leq X_j \leq 10^9
- X_1, X_2, \ldots, X_M 都是不同的
- 所有输入值均为整数
输入
N M D_1 D_2 \ldots D_N X_1 X_2 \ldots X_M
- 第一行包含计划数量 N 和路障数量 M,用空格分隔。
- 第二行包含坐标变化 每个计划的 D_1, D_2, \ldots, D_N ,用空格分隔。
- 第三行包含坐标 每个路障的 X_1, X_2, \ldots, X_M ,以空格分隔。然而,如果 M = 0,未给出第三行。
输出
在一行中打印最佳选择计划时高桥的最大可能最终坐标。
示例输入 1
4 2 3 -2 4 -1 2 5
示例输出 1
0
示例输入 2
5 0 -3 1 2 -1 4
示例输出 2
7
示例输入 3
10 6 2 5 -3 6 -4 7 -8 3 4 -2 -7 8 14 19 -11 25
示例输出 3
7
示例输入 4
20 15 5 4 -6 7 -3 8 -10 6 9 -5 4 -7 12 -8 3 11 -9 2 6 -4 -20 -13 -1 10 18 27 35 44 -7 5 14 22 31 40 50
示例输出 4
4
示例输入 5
1 1 50000 0
示例输出 5
0