← 返回题目列表

AtCoder · arc131_d

D. AtArcher射手

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

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