UOJ Logo Zijian Online Judge

ZOJ

#8. 小鱼干

统计

小喵喵有 $n$ 个小鱼干排成一列,其中第 $i$ 个小鱼干有两种属性,美味度 $a_i$ 和特殊度 $b_i$。

现在小喵喵要吃掉一些小鱼干,出于一些原因,小喵喵会吃掉连续的一段区间中的所有小鱼干。

如果吃掉了 $[l,r]$ 一段区间,那么小喵喵会获得一些满意度。

形式化地,总满意度 $ = (\sum_{i=l}^{r} a_i) × (1 + \sum_{i=l}^{r} b_i)$。

由于只有小喵喵最喜欢的小鱼干的特殊度等于 $1$,所以 $b_i=1$ 的小鱼干数量不会超过 $400$ 个,其他的 $b_i=0$。

现在小喵喵可以选择任意一段区间(不能为空),但是有一些小鱼干的美味度是负数,吃掉所有小鱼干不一定会获得最多的满意度。所以小喵喵想知道最大能获得的总满意度是多少。

输入格式

第一行一个整数 $n$,表示小鱼干的数量。

第二行 $n$ 个整数,第 $i$ 个数为 $a_i$,表示美味度。

第三行 $n$ 个整数,第 $i$ 个数为 $b_i$,表示特殊度。

输出格式

一行一个整数,表示最大的总满意度。

样例

input

5
4 -2 2 -3 1
0 0 1 0 0

output

8

限制与约定

对于 $60\texttt{%}$ 的数据,$1 \leq N \leq 1000$。

对于另外 $20\texttt{%}$ 的数据,所有 $b_i=0$。

对于另外 $10\texttt{%}$ 的数据,保证 $b_i=0$ 的 $i$ 不会超过 $20$。

对于 $100\texttt{%}$ 的数据,$1 \leq N \leq 100000$,$0 \leq |a_i| \leq 10^9$,$0 \leq b_i \leq 1$,保证 $b_i=1$ 的 $i$ 不会超过 $400$。

时间限制:$1\texttt{s}$

空间限制:$512\texttt{MB}$

下载

样例数据下载