题目背景

来源：https://www.gitlink.org.cn/thusaa/thuwc2018。

2018 清华大学信息学冬季体验营（THUWC 2018）D2T1。$\texttt{7s,0.5G}$。

题目描述

小 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

见附件中的 ex_2.in。

见附件中的 ex_2.ans。

提示

对于 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$ 分。各个数据点的限制如下：