题目描述

りんごさん参加了射箭比赛“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$。

现在，已知りんごさん已经射完所有的箭，请问她最多能获得多少分？

输入格式

输入通过标准输入给出，格式如下：

$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

输出

270

样例 2

输入

3 3 8
0 2 7 9
100 70 30

输出

200

样例 3

输入

7 5 47
0 10 40 100 160 220
50 25 9 6 3

输出

111

样例 4

输入

100 1 5
0 7
100000000000

输出

300000000000

样例 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

输出

119

说明/提示

限制条件

• $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$
• 所有输入均为整数

样例解释 1

本样例对应题目中的例子，但 $D = 3$。例如，将 $N = 3$ 支箭分别射在坐标 $-6, -2, 1$，可以分别获得 $70, 100, 100$ 分。此时总得分为 $270$ 分，是可实现的最大得分。 需要注意，不能将所有箭都射入 $100$ 分区域获得 $300$ 分，因为任意两支箭之间必须至少间隔 $D = 3$，否则会被判定为失格，总得分为 $0$。

样例解释 2

本样例也对应题目中的例子，但 $D = 8$。例如，将 $N = 3$ 支箭分别射在坐标 $-7, 1, 9$，可以分别获得 $70, 100, 30$ 分。此时总得分为 $200$ 分，是可实现的最大得分。

样例解释 3

例如，如下图所示射箭时，总得分为 $111$ 分，这是最大值。

样例解释 4

虽然可以射 $N = 100$ 支箭，但为了不被判定为失格，在有得分的区域内最多只能放入 $3$ 支箭。

由 ChatGPT 4.1 翻译