题目描述

FJ 的 $2n$ 头奶牛准备举办一场音乐会。其中 $n$ 头奶牛是手风琴手，另外 $n$ 头奶牛是班卓琴手，每个手风琴手有一个天才指数 $a_i$，每个班卓琴手也有一个天才指数 $b_i$。 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$。

数据规模与约定

对于 $100\%$ 的数据，$3 \leq n \leq 10^3$，$0 \leq a_i,b_i \leq 10^3$。

题目来源

Gold