题目描述
小 R 为了看日出，来到了 C 国的东海岸。
东海岸的海岸线上从北到南依次排列着 $n$ 座城市，编号为 $1$ 到 $n$。其中编号小的城市在编号大的城市的北边。相邻编号之间的城市由海滨公路连接，连接城市 $i$ 和 $i+1$ 的公路长度为 $l_i$ 公里。
小 R 有一辆汽车，这辆汽车每行驶一公里需要消耗一单位的汽油。在城市之间的道路上没有加油站，因此小R只能选择在路途中的城市里加油。城市 $i$ 每单位汽油的价格是 $p_i$。小R的汽车在消耗完所有的汽油之后就会立刻熄火，无法前进，且小R的汽车油箱最多能装 $V$ 单位汽油。
小 R 一共规划了 $m$ 次看日出的行程，在第 $i$ 次行程中，小 R 晚上住在 $s_i$ 号城市，第二天凌晨要开车赶往 $t_i$ 号城市看日出。由于某些原因，小 R 总是会从编号较小的城市赶往编号较大的城市，即满足 $s_i < t_i$ 。因为行程的时间非常紧张，所以每次行程小 R 都会选择距离最短的路线。在选择最短路线的基础上，小 R 希望合理安排加油的地点，使得每次行程的花费最小。在第 $i$ 次行程刚开始时，小 R 的汽车油箱的油量为 $v_i$（$0\le v_i\le V$）。
注意，每次行程都是相互独立的，第 $i$ 次行程刚开始的油箱的油量总是 $v_i$，不会受到上一次行程结束时油箱中剩余油量的影响。
输入格式
第一行三个用空格隔开的正整数$n，m，V$，分别表示城市的数量，行程的数量和油箱容量。
第二行 $n$ 个用空格隔开的正整数，第 $i$ 个正整数表示 $p_i$。
第三行 $n-1$ 个用空格隔开的正整数，第 $i$ 个正整数表示 $l_i$。
接下来 $m$ 行，每行三个用空格隔开的整数 $s_i$，$t_i$，$v_i$，表示第 $i$ 次行程小 R 要从 $s_i$ 出发赶往 $t_i$，出发时油箱里有 $v_i$ 单位汽油。
输出格式
输出 $m$ 行，第 $i$ 行表示第 $i$ 次行程的最小花费。
样例一
输入
6 5 5
1 6 2 3 5 1
1 2 4 3 4
1 6 1
2 6 1
2 6 5
3 5 1
3 4 5输出
32
38
26
14
0样例二
输入
10 10 10
3 6 6 5 1 1 9 4 1 6
3 1 2 1 3 7 7 1 3
4 8 5
2 7 6
2 9 5
1 5 3
4 7 8
3 4 6
1 3 3
1 2 6
3 7 1
2 5 1输出
45
8
52
12
3
0
3
0
21
17子任务
对于 100% 的数据，$n\le10^6$，$m\le10^6$，$1\le V\le 10^{18}$，$1\le s_i< t_i \le n$，$0\le v_i \le V$，$1\le l_i\le\min(V,10^6)$，$1\le p_i\le5\times10^6$。
本题共 20 个数据点，每个数据点 5 分。各个数据点的限制如下：
| 测试点编号 | $n=$ | $m=$ | $V$ | 其它约定 |
|---|---|---|---|---|
| $1$ | $10$ | $10$ | $\le 10$ | 无 |
| $2\sim 3$ | $10^3$ | $10^3$ | $\le 10^{18}$ | 无 |
| $4\sim 8$ | $10^5$ | $10^5$ | $\le 10^{18}$ | 无 |
| $9\sim 11$ | $5\times 10^5$ | $5\times 10^5$ | $\le 10^{18}$ | $s_i=1$ |
| $12,13$ | $5\times 10^5$ | $5\times 10^5$ | $= 10^{18}$ | 无 |
| $14,15$ | $5\times 10^5$ | $5\times 10^5$ | $\le 10^{18}$ | 无 |
| $16\sim 20$ | $10^6$ | $10^6$ | $\le 10^{18}$ | 无 |
QOJ 中的 Hack 数据不受表格中等号限制。
在提交代码后将为你评测预测试数据并返回结果。本题的预测试数据包含 $7$ 个测试点，第 $i$ 个测试点满足表格中第 $i+1$ 行的数据规模限制。
注意：预测试数据的评测结果与最终评测结果没有关系。