### 问题描述

大衣有 $N$ 根百醇，百醇是一种夹心的巧克力棒，其宽度和厚度可以忽略不计，第 $i$ 根百醇的长度为 $A_i$，它的美味值为 $B_i​$。

大衣想在吃掉它们之前将它们玩弄一番，他可以不按原始的顺序地将百醇一根接一根地摆放在一个坐标轴上，坐标从 $0$ 开始。

定义 $x_i$ 为第 $i$ 根百醇摆放开始位置的坐标，百醇总美味值为 $\sum\limits_{i=1}^N x_i\cdot B_i$。

大衣想让百醇的总美味值最大，你能告诉他是多少吗？

注意：第一根百醇摆放开始位置的坐标必须是 $0$，并且两根相邻的百醇之间不能有间隙，即必须首尾相接。

输入格式

第一行输入一个正整数 $T$ 表示测试数据的组数。

接下来 $T$ 组测试数据每组输入三行：

• 第一行输入一个正整数 $N$ 表示百醇的数量。

• 第二行输入 $N$ 个整数 $A_1,A_2,\cdots,A_N$ 表示百醇的长度。

• 第三行输入 $N$ 个整数 $B_1,B_2,\cdots,B_N$ 表示百醇的美味值。

输出格式

对于每组测试数据，输出百醇最大的总美味值，并换行。

样例输入

2
2
1 2
4 6
4
2 8 9 11
25 27 100 45

样例输出

8
2960

说明

样例 $1$：将第 $2$ 根百醇放在第 $1$ 根后面，此时 $x_2=0,x_1=2$，百醇的总美味值为 $2\cdot4+0\cdot6=8​$，可以证明没有比这更大的总美味值。

样例 $2$：按照 $[2,4,3,1]$ 的顺序摆放，此时 $x=[28,0,19,8]$，百醇的总美味值为 $28\cdot25+0\cdot27+19\cdot100+8\cdot 45=2960$，可以证明没有比这更大的总美味值。

评测数据规模

对于所有的评测数据，$1\le T\le 20$，$1\le N\le 10^4$，$1\le A_i,B_i\le10^4$。