题目描述

A 公司正在热销某计算机产品，作为 A 公司 CEO 的小 A 打算为接下来连续的 $N$ 个销售季度制定一份具体的生产和销售方案。 已知第 $i$ 个销售季度该产品的订购量为 $D_i$，在第 $i$ 个季度，A 公司会通过如下几种方式来解决用户的订购需求：

○ 在第 $i$ 个季度生产新的产品来销售。

○ 若在第 $i$ 个季度以前库存还有多余的产品，则可以直接在第 $i$ 个季度销售(注意第一个季度之前没有任何库存产品)。

○ 在第 $i$ 个季度可以不完成全部的订购需求，而将未完成的订购需求推迟，归入到下一个季度$(i + 1)$的产品订购需求中。

A 公司需要考虑以下几种耗费： 生产新产品的成本耗费、库存产品的额外储存耗费以及推迟订购需求而需要赔偿给用户的损失费。另外由于劳力和资源的限制，每个销售季度能够生产新产品的数量是有限的，各季度的耗费和可以生产的产品上限数也不尽相同，具体如下：

○ 在第 $i$ 个季度最多可以生产 $U_i$ 件新的产品，每一件的成本为 $P_i$。

○ 第 $i$ 个季度保存下来的产品，可以用于以后季度的销售。对于每一件产品，若从第 $i$ 季度保存到第 $i + 1$ 季度， 需要额外支付 $M_i$ 的存储费用(注意产品保存到下个季度后可能再次库存)。

○ 对于第 $i$ 个季度需要推迟而归入到下一个季度订购需求的每一件产品， A 公司需要赔偿给用户损失费 $C_i$(注意延迟到下个季度可能再次被延迟, 费 用按后面季度的延迟费用计)。

在第 $N$ 个季度结束后， A 公司必须解决之前所有的用户订单。可以保证， A公司能够生产的产品总数不会低于总订购量， 也就是说一定存在一组生产和销售方案使得满足所有的用户订购需求。小 A 想知道如何来安排产品的生产和销售，使得在满足所有订购需求的前提下公司总的耗费最小。

输入格式

输入文件 $\tt{product.in}$ 第一行是一个正整数 $N$，表示有 $N$ 个销售季度。

第二行有 $N$ 个非负整数 $D_1$, $D_2$, .., $D_N$，表示第 $i$ 个季度的订购量。

第三行有 $N$ 个非负整数 $U_1$, $U_2$, .., $U_N$，表示第 $i$ 个季度最多可以生产的新的产品数。

第四行有 $N$ 个非负整数 $P_1$, $P_2$, .., $P_N$，表示第 $i$ 个季度生产一件新产品的成本。

第五行有 $N - 1$ 个非负整数 $M_1$, $M_2$, ..,$M_{N-1}$，表示将一件产品从第 $i$ 个季度保存到第 $i +1$ 个季度所需要的额外的耗费。

第六行有 $N-1$ 个非负整数 $C_1$, $C_2$, .., $C_{N-1}$，表示一件产品的订购需求在第 $i$ 个季度没有完成而归入到第 $i +1$ 个季度的订购量中，需要赔偿给用户的损失费。

输出格式

输出文件 $\tt{product.out}$ 仅包含一个非负整数，表示公司的最小总耗费。

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

30

提示

【样例说明】

第一个季度生产 $2$ 件产品，第二个季度生产 $5$ 件产品，第三个季度不生产产品，第四个季度生产 $1$ 件产品，成本为 $2 * 5 + 5 * 1 + 0 * 5 + 1 * 5 = 20$。

因为第一个季度最多只能生产 $2$ 件产品，无法满足 $3$ 件的订购量，因此将 $1$件产品的订购量推迟到第二个季度，赔偿给用户的损失费为 $5$。

第二个季度由于第一个季度推迟了一件产品的订购需求， 因而订购量变为 $3$。该季度生产了 $5$ 件产品，剩下的 $2$ 件保存下来。第三个季度直接销售库存的产品，再多出来的 $1$ 件产品继续储存到第四个季度，加上第四个季度生产了 $1$ 件产品，因此满足了所有订单需求。总的储存费用为 $2 * 2 + 1 * 1 = 5$。

总的费用为 $20 + 5 + 5 = 30$。

【数据规模】

对于 $30\%$的数据， $N \leq 1,000$。

对于 $100\%$的数据， $1 \leq N \leq 100,000$， $1 \leq D_i, U_i, P_i, M_i,C_i \leq 10,000$。