题目描述

给定两个长度为 n 的整数列 A 和 B ，每次你可以从 A 数列的左端或右端取走一个数。假设第 i 次取走的数为 $A_x$，则第i次取走的数的价值 $v_i = b_i \times a_x$ ，现在希望你求出 $\sum_{i=1}^n v_i$ 的最大值。

数据范围： $1 \le n \le 1000$ ,$1 \le A_i,B_i \le 1000$

输入格式

第一行输入一个正整数 n ，表示数列 A 和 B 的长度。

第二行和第三行各输入 n 个正整数，分别表示数列 A 和 B 的元素

输出格式

按题目要求输出最大值

样例 #1

样例输入 #1

2
1 1000
2 1

样例输出 #1

2001