该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

问题描述

小A给出 $2^k-1$ 个数 $a_1,a_2,...,a_{2^k-1}$。

小B给出 $k$ 个数 $b_0,b_1,...,b_{k-1}$。

而你是小C，需要给出 $2^k-1$ 个数 $c_1,c_2,...,c_{2^k-1}$，满足对于所有 $j=0...k-1$：

成立，你需要求出所有情况下 $\sum_{i=1}^{2^k-1}a_i*c_i$ 的最大值。

输入格式

多组询问，第一行一个数 $T$ 表示数据组数。

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

接下来一行 $2^k−1$ 个数，表示 $a_1,a_2,…,a_{2^k−1}$。

接下来一行 $k$ 个数，表示 $b_0,b_1,…,b_{k−1}$。

输出格式

对于每组询问，输出一个数，表示答案。

样例输入

3
2
1 2 4
4 5
3
3226252 19270256 2430652 1187613 12496062 10286165 17494834
24 85 34
4
901133 6693218 13245489 14740234 16186210 11382783 19277321 3855635 16523184 10168517 16195031 971041 10303441 8395899 11618555
529321239 218214127 92942310 207467810

样例输出

18
1949753378
7832404777567179

数据范围

对于 $10\%$ 的数据，$k\le 2$。

对于 $30\%$ 的数据，$k\le 3$。

对于另外 $20\%$ 的数据，$a_i,b_i$ 随机生成。

对于$100\%$ 的数据，$T\le100,2\le k\le4,0\le a_i\le10^8, 1\le b_i\le 10^9$​。