题目描述

给定两个长度为 $n$ 的整数列 $A$ 和 $B$ ，每次你可以从 $A$ 数列的左端或右端取走一个数。

假设第 $i$ 次取走的数为 $a_x$ ，则第 $i$ 次取走的数的价值 $v_i=b_i⋅a_x$ ，现在希望你求出 $∑v_i$ 的最大值。

输入格式

第一行一个数 $T$ ，表示有 $T$ 组数据。

对于每组数据，第一行一个整数 $n$ ，

接下来两行分别给出 $A$ 数列与 $B$ 数列。

输出格式

每一组数据输出一行，最大的 $∑v_i$。

样例输入输出

样例输入

2
2
1 1000
2 1
5
1 3 5 2 4
1 2 3 4 5

样例输出

2001
52

数据范围

对于 $100%$ 的数据，保证 $T≤10,1≤n≤10^3,1≤a_i,b_i≤10^3$ 。