小琳想要做杯子蛋糕給小艾吃，於是準備了 $\color{black}{n}$ 個麵團，編號 $\color{black}{1\sim n}$，每個麵團有新鮮度 $\color{black}{a_1\sim a_n}$，和美麗度 $\color{black}{b_1\sim b_n}$。

小琳可以把連續區間的麵團疊起來，做成一個杯子蛋糕，假設選的區間是 $\color{black}{[l,r]}$，則編號 $\color{black}{l}$ 的麵團會被疊在最下面，編號 $\color{black}{r}$ 的麵團會被疊在最上面，越上面的麵團貢獻的新鮮度就會越大。每個杯子蛋糕最後的好吃度除了疊起來的麵團貢獻的新鮮度外，也會加上被前一個杯子蛋糕的美麗度影響的好吃度。

由疊起來的麵團貢獻的好吃度計算如下：最下層的麵團新鮮度可貢獻 $\color{black}{1}$ 倍好吃度，第二層貢獻 $\color{black}{2}$ 倍，最上層貢獻 $\color{black}{r-l+1}$ 倍，所以好吃度總共為 $\color{black}{\sum_{i=l}^{r}(i-l+1)\times a_i}$。

由前一個杯子蛋糕美麗度影響的好吃度計算如下，因為前一個杯子蛋糕最上層麵團的美麗度為 $\color{black}{b_{l-1}}$，所以最後會貢獻 $\color{black}{b_{l-1}\times\sum_{i=l}^{r}a_i}$ 的好吃度，如果前面沒有杯子蛋糕，也就是 $\color{black}{l=1}$，那麼此值可忽略。

一個杯子蛋糕最後的好吃度 $\color{black}{D(l,r)}$ 等於由疊起來的麵團貢獻的好吃度加上前一個杯子蛋糕的美麗度計算後的好吃度，也就是 $\color{black}{D(l,r)=\sum_{i=l}^{r}(i-l+1)\times a_i+b_{l-1}\times\sum_{i=l}^{r}a_i}$。小琳想把所有麵團分成若干個互不重疊的區間，且把這些區間的麵團都疊成杯子蛋糕，每個麵團都會被用到，問最後所有杯子蛋糕好吃度總和最大可以是多少？

就是要你找 $\color{black}{(l_1,r_1)\sim(l_k,r_k)，l_1 = 1, r_k = n, r_i+1=l_{i+1}}$，使 $\color{black}{\sum_{i=1}^{k}D(l_i,r_i)}$ 最大。