问题陈述

Ringo参加了一个名为AtArcher的射箭比赛。

在AtArcher中，参与者向一条数轴上的目标射击$N$支箭来争夺总得分。目标的中心位于坐标$0$处。根据箭所击中的位置，得分定义如下。

• 对于$i = 0，1，\dots，M-1$，如果箭射中离目标中心的距离在$r_i$和$r_{i+1}$之间，则得分为$s_i$。如果距离大于$r_M$，则得分为$0$。如果箭射中边界，则应用更高的得分。
• 越靠近中心，得分越高。换句话说，满足以下条件。
  • $0 = r_0 < r_1 < \cdots < r_{M-1} < r_M$
  • $s_0 > s_1 > \cdots > s_{M-1} > 0$

例如，下图显示了当$r = (0, 2, 7, 9), s = (100, 70, 30)$时的射击得分。

此外，AtArcher还有一个特殊规则：任意两支箭之间的距离必须至少为$D$。违反此规则将使参与者被取消资格，总得分为$0$。

Ringo可以从所有射击中获得的最大总得分是多少？

约束条件

• $1 \leq N \leq 10^5$
• $1 \leq M \leq 10^5$
• $1 \leq D \leq 10^6$
• $0 = r_0 < r_1 < \cdots < r_{M-1} < r_M \leq 10^{11}$
• $10^{11} \geq s_0 > s_1 > \cdots > s_{M-1} > 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