题目描述

FJ 的 $2N$ 头奶牛（$3 \leq N \leq 1000$）准备举办一场音乐会。其中 $N$ 头奶牛是手风琴手，另外 $N$ 头奶牛是班卓琴手，每个手风琴手有一个天才指数 $A_i$（$0 \leq A_i \leq 1000$），每个班卓琴手也有一个天才指数 $B_i$（$0 \leq B_i \leq 1000$）。

FJ 需要给手风琴手和班卓琴手配对。让第 $i$ 位手风琴手和第 $j$ 位班卓琴手配对，能产生 $A_i \times B_j$ 的收益。

不幸的是，FJ 的奶牛都存在一种怪癖：如果第 $i$ 位手风琴手和第 $j$ 位班卓琴手配对，那么第 $i+1 \sim N$ 位手风琴手，不会选择与第 $1 \sim j-1$ 位班卓琴手配对。这给 FJ 的配对计划带来了很多不便。

更糟糕的是，那些失去演出机会的失落的奶牛，为了消解内心的失落感情，会成群结队地到酒吧喝酒。

如果第 $x$ 号手风琴手到第 $y$ 号手风琴手都是失落的（$x-1$ 和 $x+1$ 号手风琴手不存在或是参加了演出），这些奶牛就会去结队去酒吧喝酒，开销为：

对于班卓琴手，也有类似的规律。

现在 FJ 不得不好好考虑下他的计划了，他想让你算出他的最大的收益。

输入格式

第一行一个整数 $N$。

接下来 $N$ 行，每行一个整数 $A_i$。

接下来 $N$ 行，每行一个整数 $B_i$。

输出格式

输出 FJ 能获得的最大收益。

3
1
1
5
5
1
1

17

提示

手风琴手 $3$ 和班卓琴手 $1$ 搭配，收益 $25$。

手风琴手 $1,2$ 一块喝酒，花费 $4$。

班卓琴手 $2,3$ 一块喝酒，花费 $4$。

最终收益为 $17$。