#1971. 取数游戏

取数游戏

题目描述

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

数据范围: 1n10001 \le n \le 1000 ,1Ai,Bi1000 1 \le A_i,B_i \le 1000

输入格式

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

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

输出格式

按题目要求输出最大值

样例 #1

样例输入 #1

2
1 1000
2 1

样例输出 #1

2001