给定 $2^k - 1$ 个数 $c_1, c_2, \dots, c_{2^k-1}$ 和 $k$ 个数 $a_0, a_1, \dots, a_{k-1}$。 你需要找到非负整数 $x_1, x_2, \dots, x_{2^k-1}$，使得对于所有 $j$ ($0 \le j < k$)，满足： $$\sum_{i=1}^{2^k-1} \lfloor i/2^j \rfloor \bmod 2 \cdot x_i = a_j$$ 并且使得 $\sum_{i=1}^{2^k-1} x_i c_i$ 最大化。
输入格式
第一行包含一个整数 $T$ ($1 \le T \le 100$)，表示测试用例的数量。 对于每个测试用例： 第一行包含 $k$ ($2 \le k \le 4$)。 第二行包含 $c_1, c_2, \dots, c_{2^k-1}$ ($0 \le c_i \le 10^8$)。 * 第三行包含 $a_0, \dots, a_{k-1}$ ($1 \le a_i \le 10^9$)。
输出格式
对于每个测试用例，输出一个整数，即最大值。
样例
输入 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
输出 1
18 1949753378 7832404777567179