题目描述

最近徐老师玩的游戏出了一个新的活动——帮会战

于是徐老师准备带着公会里一共 $n$ 个玩家（编号分别为 $1 \sim n$）出战！

其中第 $i$ 个玩家的战斗力为 $a_i$

由于是新的活动，为了尽可能站稳 "第一帮会" 的地位，徐老师给每个玩家配备了附魔道具！

他给第 $i$ 个玩家配备的附魔道具的附魔效果为 $b_i$

具体来说，对于第 $i$ 个玩家，他原本的战斗力为 $a_i$，当他拿到附魔效果为 $b_i$ 的附魔道具时，他的战斗力就会变成 $a_i * b_i$

但是玩家们很快就发现，如果适当的调换附魔道具，可以使得整个帮会的战斗力更高

可是活动马上就开始了，徐老师没有那么多时间去考虑最优方案，也没有时间给玩家们互相调换附魔道具了

现在徐老师决定将一部分玩家的附魔道具进行交换——他会选择一段连续编号的玩家，将他们手里的附魔道具的顺序 倒置

例如对于 $3,4,5,6,7$ 五名玩家，原本他们对应拿到的附魔道具编号为 $3,4,5,6,7$，但是徐老师调换他们的道具后，他们拿到的附魔道具编号会变成 $7,6,5,4,3$

现在徐老师想知道，在最多进行一次交换的情况下（也可以不交换），帮会的总战斗力最大可以达到多少？

输入格式

输入第一行一个整数 $n$，表示玩家和附魔道具的数量。

输入第二行包含 $n$ 个整数，分别表示每个玩家原本的战斗力 $a_i$。

输入第三行包含 $n$ 个整数，分别表示每个附魔道具的附魔效果 $b_i$。

输出格式

输出一个整数表示徐老师帮会的总战斗力最大值

数据范围

本题共 $20$ 个测试点，对于全部数据 $1\le n \le 5000,1\le a_i,b_i \le 10^7$。

具体数据点分布如下：

测试点	$n\le$	$a_i,b_i\le$	特殊性质
$1 \sim 2$	$10$	$100$	无
$3 \sim 4$	$100$	$1000$
$5 \sim 10$	$200$	$10^4$
$11$	$5000$	$10^7$	保证 $a_i$ 按照从小到大的顺序给出，$b_i$ 按照从大到小的顺序给出
$12$			保证 $a_i$ 按照从大到小的顺序给出，$b_i$ 按照从小到大的顺序给出
$13 \sim 14$		$200$	无
$15 \sim 20$		$10^7$

样例输入1

5
1 2 3 4 5
2 3 4 5 6

样例输出1

70

样例解释1

不进行交换可以使得战斗力最大达到 $1 * 2 + 2 * 3 + 3 * 4 + 4 * 5 + 5 * 6 = 70$

样例输入2

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

样例输出2

235

样例解释2

交换编号 $3,4,5$ 的三个玩家手里的附魔道具可以得到最大的战斗力之和，即 $1 * 5 +8 * 9 + 7 * 8 + 6 * 8 + 3 * 6 + 6 * 6 = 235$