K. Knapsack Problem
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

You are given $$$2^k - 1$$$ numbers $$$c_1, c_2, \dots, c_{2^k-1}$$$ and $$$k$$$ numbers $$$a_0 ,a_1, \dots a_{k-1}$$$.

You want to find nonnegative integers $$$x_1, x_2, \dots, x_{2^k-1}$$$ such that for all $$$j$$$ $$$(0\leq j \lt k)$$$ $$$$$$\sum_{i=1}^{2^k - 1} \left(\lfloor i / 2 ^j \rfloor \bmod 2\right) x_i = a_j$$$$$$ holds and $$$\sum_{i=1}^{2^k - 1}x_i c_i$$$ is maximized.

Input

In the first line, $$$T$$$ ($$$1\leq T\leq 100$$$) — the number of test cases.

For each test case:

  • In the first line, $$$k$$$ ($$$2\leq k \leq 4$$$).
  • In the second line, $$$c_1, c_2, \dots, c_{2^k - 1}$$$ ($$$0\leq c_i\leq 10^8$$$).
  • In the third line, $$$a_0, \dots, a_{k - 1}$$$ ($$$1\leq a_i\leq 10^9$$$).
Output

For each test case, one integer — the answer.

Example
Input
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
(There won't be extra line breakers \
in the actual test cases.)
529321239 218214127 92942310 207467810
Output
18
1949753378
7832404777567179