乘积和的最大值

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定两个长度均为 $n$ 的整数数组 $a$ 和 $b$。你可以至多选择一次数组 $a$ 的连续子数组并将其翻转。

求操作后 $\sum_{i=1}^{n}a_i b_i$ 的最大可能值。

输入格式

第一行包含一个整数 $n$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

第三行包含 $n$ 个整数 $b_1,b_2,\ldots,b_n$。

输出格式

输出一个整数，表示至多翻转一次连续子数组后能得到的最大乘积和。

样例输入 1

5
2 3 2 1 3
1 3 2 4 2

样例输出 1

29

样例输入 2

2
13 37
2 4

样例输出 2

174

样例输入 3

6
1 8 7 6 3 6
5 9 6 8 8 6

样例输出 3

235

数据范围

$1\le n\le5000$，$1\le a_i,b_i\le10^7$。