说明

假期将至，山姆计划去看望他的父母。有 $N$ 座城市，编号从 $1$ 到 $N$。山姆住在城市 $1$ 的大学宿舍，而他的父母住在城市 $N$。

山姆对各个城市已经做了一些研究。他为每个城市 $i$ 赋予了一个整数 $H_{i}$，表示如果他访问该城市（包括城市 $1$ 和城市 $N$）所能获得的“幸福值”。

至于交通方式，他发现对于每个满足 $1 \leq i < N$ 的城市，都有一趟单向巴士，该巴士从城市 $i$ 出发，并在城市 $i+1$ 到城市 $i+T_{i}$ 之间的每个城市停靠；换言之，巴士会停靠接下来的连续 $T_{i}$ 个城市。保证 $i + T_{i} \leq N$。当山姆位于城市 $i < N$ 时，他会乘坐从城市 $i$ 出发的巴士，并在城市 $j$ 下车，其中 $j \in (i+1, i+T_{i}]$，并且会跳过城市 $i$ 和 $j$ 之间的所有站点（不含 $i$ 和 $j$）。注意，如果山姆在城市 $i$，他不能乘坐不是从城市 $i$ 出发的巴士。

山姆喜欢快乐，但不喜欢长时间待在巴士上（他很容易感到无聊）。具体来说，如果他乘坐从城市 $i$ 出发并在城市 $j$ 下车的巴士（其中 $i < j$），他的幸福值会减少以下数量：

$$\left\lfloor \frac{j - i}{K} \right\rfloor \times D$$

山姆正忙着为父母准备纪念品，并思考到达后要做的事情。所以他需要你的帮助，计算他通过精心规划从城市 $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$，如下列计划所示：

• 山姆从城市 $1$ 出发。他在城市 $1$ 获得幸福值 $H_{1} = 8$。
• 在城市 $1$，山姆乘坐可停靠 $[2, 6]$ 中任意城市的巴士，并在城市 $4$ 下车。此次巴士行程使他的幸福值减少 $\left\lfloor \frac{4-1}{2} \right\rfloor \times 1 = 1$。他在城市 $4$ 获得幸福值 $H_{4} = 9$。
• 在城市 $4$，山姆乘坐可停靠 $[5, 6]$ 中任意城市的巴士，并在城市 $5$ 下车。此次巴士行程使他的幸福值减少 $\left\lfloor \frac{5-4}{2} \right\rfloor \times 1 = 0$。他在城市 $5$ 获得幸福值 $H_{5} = 0$。
• 在城市 $5$，山姆乘坐可停靠 $[6, 6]$ 中任意城市的巴士，并在城市 $6$ 下车。此次巴士行程使他的幸福值减少 $\left\lfloor \frac{6-5}{2} \right\rfloor \times 1 = 0$。他在城市 $6$ 获得幸福值 $H_{6} = 2$。

此计划中，山姆共乘坐 $3$ 次巴士，总幸福值为 $8 + (-1 + 9) + (0 + 0) + (0 + 2) = 18$。在此例中，没有其他计划能得到更高的总幸福值。

输入格式

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

输出格式

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

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

18

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

15

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

-9

提示

样例 #2 解释

在城市 $1$，山姆乘坐可停靠 $[2, 6]$ 中任意城市的巴士，并在城市 $3$ 下车。在城市 $3$，山姆乘坐可停靠 $[4, 8]$ 中任意城市的巴士，并在城市 $8$ 下车。此计划的总幸福值为 $10 + (\left\lfloor \frac{3-1}{8} \right\rfloor \times 8 - 5) + (\left\lfloor \frac{8-3}{8} \right\rfloor \times 8 + 10) = 8 + (0 - 5) + (0 + 10) = 15$。

翻译由 DeepSeek 完成