A38690.重复の任务

孜孜不倦地做任务……？

JW 的学校举办了一个线上活动，参加者需要完成 $N$ 个任务就可以获得超级大礼。JW 当然是要参加的。但是，学校为了培养学生们的思维，所有任务都非常的复杂。

JW 觉得任务很简单，不就是给同学们送祝福，然后统计送祝福数量和收到“同祝”数量吗。他直接设 $f(x)$ 表示第 $x$ 个任务的送祝福数量与收到“同祝”数量的和，最后答案就是 $\sum_{i=1}^N f(i)$。JW 有无数个男同学和女同学，第 $1$ 个任务需要给 $a_1$ 个男同学送祝福，再给 $b_1$ 个女同学送祝福，然后，会收到 $\max(a_1,b_1)$ 个“同祝”。

接下来的任务就没那么简单了。对于第 $i$ 个任务（$i \geq 2$），需要完成第 $a_i,a_i+1,a_i+2,\ldots,b_i$ 个任务，然后会收到 $\max_{0 \leq j \leq b_i-a_i}f(a_i+j)$ 个“同祝”。当然，最后这些任务都会转化成若干个任务 $1$。

但是，JW 的精力毕竟是有限的，处理每个任务也是需要花费一定的精力的。现在我们认为 JW 的精力是 $w_0$，处理好第 $i$ 个任务的精力花费是 $w_i$，但是可以获得 $f(i)$ 个“同祝”。然而，第 $i$ 对同学可能有 $k_i$ 个一模一样的任务。。JW 为了让他的 rp++，肯定是要积累最多的“同祝”数量，所以现在请你帮他算出来在他的精力用完前最多能收集到多少个的“同祝”。

输入共 $5$ 行：

第一行有 $1$ 个正整数 $N$，含义见题目描述；

第二行有 $N$ 个正整数 $a_i$，含义见题目描述；

第三行有 $N$ 个正整数 $b_i$，含义见题目描述；

第四行有 $N+1$ 个正整数 $w_i(0 \rightarrow N)$，含义见题目描述；

第五行有 $N$ 个正整数 $k_i$，含义见题目描述。

输出一个数，表示 JW 在精力用完前能累计多少个“同祝”。

【数据范围】

对于所有数据，保证：

$1 \leq N \leq 5 \times 10^3$，$1 \leq a_1,b_1 \leq 10^5$，$1\leq w_i \leq500$，$1\leq k_i \leq10^3$，$1 \leq a_i \leq b_i < i$（$i \geq 2$），$w_i\le w_0$（$i\geq1$）

测试点	$N\le$	$k\le$	特殊性质
1	$10$	$1$	无
2	$100$	$500$	无
3,4,5	$10^3$	$500$	A
6	$10^3$	$500$	B
7,8,9	$10^3$	$500$	无
10	$5 \times 10^3$	$500$	B
11	$5 \times 10^3$	$1$	无
12~20	$5\times 10^3$	$10^3$	无

特殊性质 A：保证有 $a_i=1,b_i=i-1$（$i \geq 2$）。

特殊性质 B：保证有 $a_1=b_1=1$。

本题测试点等分。

【样例解释】

样例组 #1：

$$f(1)=1+1+\max(1,1)=3 \\ f(2)=f(1)+f(1)=6 \\ f(3)=f(1)+f(2)+\max(f(1),f(2))=15$$

JW 共有 $10$ 点精力，完成每个任务分别需要 $\{10,5,5\}$ 点精力，一种可能的最优的方式是选择完成第 $2$ 和 $3$ 个任务各 $1$ 次，可获得 $f(2)+f(3)=21$ 个“同祝”。

样例组 #2:

$$f(1)=3+4+\max(3,4)=11 \\ f(2)=f(1)+f(1)=22 \\ f(3)=f(1)+f(1)=22 \\ f(4)=f(1)+f(1)=22$$

JW 共有 $8$ 点精力，完成每个任务分别需要 $\{2,4,1,1\}$ 点精力，一种可能的最优方式是可以完成所有任务各 $1$ 次，可获得 $1\times f(1)+1\times f(2)+1\times f(3)+1\times f(4)=77$ 个“同祝”。

样例组 #3:

$$f(1)=2+4+\max(2,4)=10 \\ f(2)=f(1)+f(1)=20 \\ f(3)=f(1)+f(2)+\max(f(1),f(2))=50 \\ f(4)=f(1)+f(2)+f(3)+\max(f(1),f(2),f(3))=130$$

JW 共有 $19$ 点精力，完成每个任务分别需要 $\{10,3,7,2\}$ 点精力，一种可能的最优的方式是选择完成第 $3$ 个任务 $2$ 次和第 $4$ 个任务 $2$ 次，可获得 $2\times f(3)+2\times f(4)=360$ 个“同祝”。