Heavy and Frail
暂无测试数据。
云浅有 $n$ 种水晶，每种水晶有以下三种属性：
- $a_i$：第 $i$ 种水晶每颗的能量值。
- $b_i$：吸收一颗第 $i$ 种水晶蕴含的能量所需的时间。
- $c_i$：第 $i$ 种水晶的数量。每一颗第 $i$ 种水晶都具有同样的 $a_i,b_i$ 属性。
云浅现在要从这些水晶中选出一些，并吸收这些水晶中的能量。
不过，她的时间并不多，因此她吸收这些水晶所用时间不能超过 $m$。她想知道吸收的能量之和的最大值是多少。
云浅发现这样太简单了，因此她会进行 $q$ 次询问。每次询问中，她会给出四个正整数 $t,x,y,z$，你需要输出：
- 如果将第 $t$ 颗水晶的三个属性 $a_i,b_i,c_i$ 分别修改为 $x,y,z$，那么最多能吸收多少能量。
注意，每次询问并没有真正地进行修改。
输入格式
第一行两个正整数 $n,m$。
第二行 $n$ 个以空格隔开的正整数 $a_1,a_2,\cdots,a_n$。
第三行 $n$ 个以空格隔开的正整数 $b_1,b_2,\cdots,b_n$。
第四行 $n$ 个以空格隔开的正整数 $c_1,c_2,\cdots,c_n$。
接下来一行一个正整数 $q$。
接下来 $q$ 行，每行四个以空格隔开的正整数 $t,x,y,z$，表示一个询问。
注：输入格式中涉及的变量含义与题面描述一致。
输出格式
对于每组询问，输出一行一个正整数表示答案。
数据范围
对于 $100\%$ 的数据，$1\le n\le 5000,1\le m\le 800,1\le q\le 2\times 10^4,1\le a_i,b_i,c_i\le 10^9,\sum a_ic_i<2^{63}$。
| 测试点编号 | $n$ | $m$ | $q$ | 其他 |
|---|---|---|---|---|
| $1\sim 2$ | $\le 5$ | $\le 5$ | $\le 5$ | $c_i=1$ |
| $3\sim 4$ | $\le 50$ | $\le 50$ | $\le 50$ | $c_i\le 50$ |
| $5\sim 7$ | $\le 150$ | $\le 150$ | $\le 200$ | 无 |
| $8\sim 12$ | $\le 2000$ | $\le 100$ | $\le 2500$ | 无 |
| $13\sim 16$ | $\le 2000$ | $\le800$ | $\le 5000$ | 无 |
| $17\sim 20$ | $\le 5000$ | $\le 800$ | $\le 2\times 10^4$ | 无 |
4 10
2 9 8 3
2 5 9 1
1 1 1 1
3
1 4 1 10
2 2 5 2
1 10 2 5
40
11
50
5 20
5 2 3 1 1
9 13 17 16 6
1 9 17 1 8
5
1 3 9 1
1 1 16 9
2 4 9 12
2 1 9 11
2 2 16 1
4
3
9
6
6