P11151 [THUWC 2018] 明天的太阳会照常升起

来源：[https://www.gitlink.org.cn/thusaa/thuwc2018](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

从标准输入读入数据。 第一行三个用空格隔开的正整数$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$ 次行程的最小花费。

对于 100% 的数据，$n\le10^6$，$m\le10^6$，$1\le V\le 10^{18}$，$1\le s_i