5824 - 集训，等级5：取数游戏
Time Limit : 1 秒
Memory Limit : 128 MB
给定2个长度为n的数字序列，a1,a2,a3..an和b1,b2..bn，每次你从A的头或尾取一个数字ai,假设第i次取的数字为ak,存在ki=ak * bi，直至所有的数字都取完后，所有的ki相加的最大值，请你求出最大值
Input
第一行一个数T，表示有T组数据。 对于每组数据，第一行一个整数n， 接下来两行分别给出A数列与B数列。
Output
每一组数据输出一行最大值
Examples
Input
2 2 1 1000 2 1 5 1 3 5 2 4 1 2 3 4 5
Output
2001 52
Hint
对于第二个样例， 第一次从左边取走a1，v1=a1⋅b1=1, 第二次从左边取走a2，v2=a2⋅b2=6, 第三次从右边取走a5，v3=a5⋅b3=12, 第四次从右边取走a4，v4=a4⋅b4=8, 第五次取走剩下的a3，v5=a3⋅b5=25。 总价值∑vi=1+6+12+8+25=52
T≤10 1≤n≤10^3 1≤ai,bi≤10^3