XHM是华南师范大学的一位上进的同学。虽然平时没有表现出来，但是其实他家早早的开了一口老窖，最早的酒来自1982，产出的酒我们简称其为XHM老窖。

随着家族产业不断扩大，XHM扩建了自家的酿酒厂，掘出了长达一公里的地下室用来酿酒。

现在，XHM遇到了问题。他已经在长达一公里的地下室摆满了酒，但是由于布局问题，工人每次只能从地下室的两端取出酒卖掉。众所周知，酒的存放是需要一定代价的，但同时，随着发酵时间增长，其出售价格也不断提高。由于XHM自家的酒厂太大，他懒得算自己最多能赚多少钱，记作$XHMRichness$，希望你帮他算算。

现在，我们形式化的表示这个问题。

设XHM拥有$n$罐酒，我们可以想象这$n$罐酒摆成了一排。

每罐酒$i$都有自己的基础价格$a_i$，即生产后直接可以卖出的价格。每罐酒$i$由于发酵速度不同，存放$x$年后，其会产生$b_i*x$的增值，即可以用$b_i*x+a_i$价格卖出。当然，酒厂有一定的固定成本，每罐酒$i$若没有卖掉，每年都需要都会花费$c_i$。另外，酒也是有有效期的，每罐酒$i$必须在$d_i$年前（包括$d_i$年）卖掉，否则就会过期直接被倒掉。

从现在开始后的$n$年(从第0年开始)，每年XHM都会卖掉（或倒掉）$n$罐酒当中的一瓶，注意，由于酒厂的布局，卖掉的酒只能从剩余的酒的最左端或者最右端选择。现在，请你计算XHM在这n年中的最大利润$XHMRichness$。

增加提示1：固定成本无论是否卖出，都存在；产品价格和增值，只有卖出时才有效；产品过了有效期，卖的时候只能倒掉，即收益为0，但是固定成本不变

增加提示2：XHM可能成本大于收益，即亏本

第一行输入$n\ (n\leq 5555)$，代表酒的数量。

第二行输入$n$个整数，表示$a_i$。

第三行输入$n$个整数，表示$b_i$。

第四行输入$n$个整数，表示$c_i$。

第五行输入$n$个整数，表示$d_i$。

输出一个整数，代表XHM能赚到多少钱$XHMRichness$。

由于XHM拥有的产业巨大，因此酒的数量$n$和$XHMRichness$较大，注意使用$long \ long$保存数据。

增加提示1：固定成本无论是否卖出，都存在；产品价格和增值，只有卖出时才有效；产品过了有效期，卖的时候只能倒掉，即收益为0，但是固定成本不变

增加提示2：XHM可能成本大于收益，即亏本