思路:贪心+前缀和

对于第 $q_i$ 次询问，目标是将第 $j$ 个杯子装满，那么选择从第 $k (k\leq j)$ 个杯子开始倒水，那么 $[k, j]$ 这些杯子被装满的水均来自第 $k$ 个杯子溢出的。

选择从第 $k (k\leq j)$ 个杯子开始倒水，则需要使得$[k+1,j]$ 这些杯子都倒满，魔力值为 $z_k\times \sum\limits_{i=k}^j (x_i-y_i)$。答案即

此外,代码中使用了一个 trick，就是对于每个查询，从 $j$ 到 $1$ 来枚举从每个杯子开始倒水(而不是从$1$到$j$)，这样我们就可以维护这其中需要添加的水量。因为如果是从 $1$ 到 $j$ 来枚举，则对于每次的倒水量都需要 $O(n)$ 去查询，导致总复杂度是$O(n^3)$ ， 当然也可以直接使用前缀和来维护。

题目内容

小美是一个年轻的魔法学徒，他一直在努力学习各种魔法技能。他听说倒水魔法是一种非常强大的魔法，但也是一种非常难掌握的魔法。他早早地来到了魔法训练室，希望能够掌握这种魔法。

魔法训练室里有 $n$ 个神奇的杯子，有着不同的大，假设第 $i$ 个杯子已满，向其倒水，多余的水会正正好好流向第 $i+1$ 个杯子(如果 $i=n$ 时没有下一个杯子，不会有杯子接住此时多余的水而溢出到魔法训练室的水池）。

这些杯子有着初始固定的水量，每次练习后杯子里的水都会还原到最初状态。每次练习时，魔法黑板会告诉小美需要将哪一人杯子倒满水。因为每个杯子的材质和形状有所不同所以对其释放倒水魔法需要消耗的魔法值不同。小美想尽可能多练习，所以需要最小化每次消耗的魔法值的总量。

输入描述

第一行一个整数 $n$ ，表示杯了数量。

第二行 $n$ 个整数 $x_1,x_2,...,x_n$ ，依次表示第 $i$ 个杯子能容纳水的量（单位为毫升）。

第三行 $n$ 个整数 $y_1,y_2,...,y_n$ ，依次表示第 $i$ 个杯子初始有的水量（单位为毫升）。

第四行 $n$ 个整数 $z_1,z_2,...,z_n$ ，依次表示对第 $i$ 个杯子每添加1毫升水需要消耗的法力值。

第五行一个整数 $m$ ，表示练习的数量。

第六行 $m$ 个整数 $q_1,q_2,…,q_n$ ，依次表示第 $i$ 次练习时需要将第 $q_i$ 个杯子倒满。(每次练习过后，杯子里的水量都会还原为初始状态，不会影响到下一次练习）

$1\le n,m\le 3000，1\le y_i\le x_x \le 10^9，1\le z_i \le 300，1\le q_i\le n$

输出描述

输出第一行 $m$ 个数，依次表示每次训练时需要消耗的最小法力值。

如果杯子初始本身就是满的，则需要消耗的法力值为 $0$ 。

样例

输入

3
1 2 3
1 1 2
1 2 5
2
3 1

输出

2 0

样例解释 第一次训练，最优方案如下:

初始时杯子的水量和最大容量分别为

1/1 1/2 2/3

1. 给1号杯子(本身已满)倒水1毫升，消耗1点法力，水溢出转移到2号杯子，当前状态为1/1 2/2 2/3
2. 2.继续给1号杯子(本身已满)倒水1毫升，消耗1点法力，水溢出到2号杯子(也已满)，继续溢出到3号杯子，此时3号杯子也被成功注满水，状态为: 1/1 2/2 3/3

共消耗2点法力。可以证明没有更优方案。

第二次训练时，

初始时杯子的水量和最大容量分别为(注意不同训练互不影响，因为训练结束后魔法会让水杯还原为初始状态)

1/1 1/2 2/3

可以发现1号杯子已满，不用注水，消耗法力为0。