分数: 600 点
问题陈述
Ringo 正在参加 AtArcher 的射箭比赛。
在 AtArcher 中,一名参与者射击 N 箭头指向数轴上的目标,争夺总分。目标中心位于坐标 0。根据箭击中的位置,射击得分定义如下。
- 对于 i = 0, 1, \dots, M-1,如果箭头击中的点与目标中心的距离介于 r_i 和 r_{i+1},得分为 s_i。如果距离大于 r_M,得分为 0. 如果箭头击中边界,则应用较高的分数。
- 越靠近中心,得分越高。换句话说,满足以下条件。
- 0 = r_0 \lt r_1 \lt \cdots \lt r_{M-1} \lt r_M
- s_0 \gt s_1 \gt \cdots \gt s_{M-1} \gt 0
例如,下图显示了当 r = (0, 2, 7, 9), s = (100, 70, 30).
此外,AtArcher 有一个特殊规则:任何两个箭头之间的距离必须始终至少为 D。违反此规则将取消参赛者的资格,总分将被取消 0.
林戈从所有镜头中可以获得的最大总分是多少?
约束
- 1 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 1 \leq D \leq 10^6
- 0 = r_0 \lt r_1 \lt \cdots \lt r_{M-1} \lt r_M \leq 10^{11}
- 10^{11} \geq s_0 \gt s_1 \gt \cdots \gt s_{M-1} \gt 0
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N M D
r_0 r_1 \cdots r_{M-1} r_M
s_0 s_1 \cdots s_{M-1}
输出
打印答案。
示例输入 1
3 3 3 0 2 7 9 100 70 30
示例输出 1
270
此示例输入对应于问题陈述中的情况,其中 D = 3.
例如,如果 N = 3 箭头击中坐标 -6, -2, 1,他们得分 70, 100, 100分别为总分 270,这是可实现的最大值。
请注意,您不能点击 100- 指向所有箭头得分的区域 300,因为任意两个箭头之间的距离必须至少为 D = 3,否则将被取消资格并得分 0.
示例输入 2
3 3 8 0 2 7 9 100 70 30
示例输出 2
200
此示例输入对应于问题陈述中的情况,其中 D = 8.
例如,如果 N = 3 箭头击中坐标 -7, 1, 9,他们得分 70, 100, 30分别为总分 200,这是可实现的最大值。
示例输入 3
7 5 47 0 10 40 100 160 220 50 25 9 6 3
示例输出 3
111
例如,如果您射出如下图所示的箭头,您将得分 总共 111 ,这是最大值。
示例输入 4
100 1 5 0 7 100000000000
示例输出 4
300000000000
可以拍摄 N = 100 箭头,但为了避免取消资格,最多 3 箭可以击中具有正分数的区域。
示例输入 5
15 10 85 0 122 244 366 488 610 732 854 976 1098 1220 10 9 8 7 6 5 4 3 2 1
示例输出 5
119