假期即将来临，Sam 计划去探望他的父母。共有 $N$ 座城市，编号从 $1$ 到 $N$。Sam 住在 $1$ 号城市的校园宿舍里，而他的父母住在 $N$ 号城市。

Sam 已经对这些城市做了一些研究。他为每座城市 $i$ 分配了一个整数 $H_i$，代表如果他访问城市 $i$（包括城市 $1$ 和城市 $N$）所能获得的“幸福值”。

关于交通，他发现对于每一座城市 $1 \le i < N$，都有一辆单向巴士从城市 $i$ 出发，并在从城市 $i+1$ 到城市 $i+T_i$ 的每一座城市停靠；换句话说，巴士会在接下来的 $T_i$ 座城市停靠。保证 $i + T_i \le N$。当 Sam 在城市 $i < N$ 时，他会搭乘一辆从城市 $i$ 出发的巴士，并在城市 $j$ 下车，其中 $j \in (i+1, i+T_i]$。注意，如果 Sam 在城市 $i$，他不能搭乘不是从城市 $i$ 出发的巴士。

Sam 喜欢快乐，但他不喜欢长时间待在巴士上（他很容易感到厌烦）。具体来说，如果他搭乘了一辆从城市 $i$ 出发并在城市 $j$ 下车的巴士（其中 $i < j$），那么他的幸福值将减少以下数值： $$\left\lfloor \frac{j - i}{K} \right\rfloor \times D$$

Sam 正忙着为父母准备纪念品，并计划到达那里后要做的事情。因此，他需要你的帮助，通过仔细规划从城市 $1$ 到城市 $N$ 的旅程，计算出他能获得的最大总幸福值。

例如，设 $N = 6, K = 2, D = 1, H_{1..6} = \{8, -7, -8, 9, 0, 2\}$，且 $T_{1..5} = \{5, 3, 3, 2, 1\}$。从该示例中可以获得的最大总幸福值为 $18$，计划如下： Sam 从城市 $1$ 出发。他在城市 $1$ 获得了 $H_1 = 8$ 的幸福值。 在城市 $1$，Sam 搭乘可以在 $[2, 6]$ 范围内任意城市停靠的巴士，并在城市 $4$ 下车。由于这次巴士行程，他的幸福值减少了 $\lfloor \frac{4-1}{2} \rfloor \times 1 = 1$。他在城市 $4$ 获得了 $H_4 = 9$ 的幸福值。 在城市 $4$，Sam 搭乘可以在 $[5, 6]$ 范围内任意城市停靠的巴士，并在城市 $5$ 下车。由于这次巴士行程，他的幸福值减少了 $\lfloor \frac{5-4}{2} \rfloor \times 1 = 0$。他在城市 $5$ 获得了 $H_5 = 0$ 的幸福值。 在城市 $5$，Sam 搭乘可以在 $[6, 6]$ 范围内任意城市停靠的巴士，并在城市 $6$ 下车。由于这次巴士行程，他的幸福值减少了 $\lfloor \frac{6-5}{2} \rfloor \times 1 = 0$ 的幸福值。他在城市 $6$ 获得了 $H_6 = 2$ 的幸福值。

在这个计划中，Sam 总共搭乘了 $3$ 次巴士，总幸福值为 $8 + (-1 + 9) + (0 + 0) + (0 + 2) = 18$。在这个例子中，没有其他计划能获得比这更好的总幸福值。

输入格式

输入的第一行包含三个整数 $N, K, D$（$2 \le N \le 100\,000$；$1 \le K \le N$；$0 \le D \le 10\,000$），分别代表城市数量以及题目描述中定义的参数 $K$ 和 $D$。第二行包含 $N$ 个整数 $H_i$（$-10\,000 \le H_i \le 10\,000$），代表 Sam 访问城市 $i$ 时将获得的幸福值。第三行包含 $N-1$ 个整数 $T_i$（$1 \le T_i$；$i+T_i \le N$），对于 $1 \le i < N$，代表从城市 $i$ 出发的巴士将停靠的后续连续城市数量。

输出格式

输出一行，包含一个整数，代表可以获得的最大总幸福值。

样例

样例输入 1

6 2 1
8 -7 -8 9 0 2
5 3 3 2 1

样例输出 1

18

说明 1

这是题目描述中的示例。

样例输入 2

8 8 8
10 -5 -5 -5 -5 -5 10
5 2 5 3 2 1 1

样例输出 2

15

说明 2

在城市 $1$，Sam 搭乘可以在 $[2, 6]$ 范围内任意城市停靠的巴士，并在城市 $3$ 下车。在城市 $3$，Sam 搭乘可以在 $[4, 8]$ 范围内任意城市停靠的巴士，并在城市 $8$ 下车。该计划的总幸福值为 $10 + (\lfloor \frac{3-1}{8} \rfloor \times 8 - 5) + (\lfloor \frac{8-3}{8} \rfloor \times 8 + 10) = 8 + (0 - 5) + (0 + 10) = 15$。

样例输入 3

13 2 2
5 -4 -4 -1 7 -6 -5 -4 -3 -2 -1 5 -7
3 10 9 8 7 6 5 4 3 2 1 1

样例输出 3

-9