Network is becoming more and more important in the modern times. There are hundreds million of people studying,researching and playing with the Internet. However, we can't forget that there will be a lot of cost when the network is running. So charging from the users is necessary and of course reasonable.

The very very famous Southern Moutain high School in the City of Soft Sheep has such a network of education. There are 2^N users in total, which are numbered 1,2,3...2^N . These users are connected by routers and cables.

Users,routers,cables make a Full Binary Tree together. Each leaf(colored white) of the tree denotes a user,each non-leaf node(colored gray) denotes a router,each edge denote a cable,see the following picture.

The charge mode of the network company in the city of Soft Sheep is quite strange, so called "Pairing Charging". It means that they charge from each two users i and j (1 <= i < j <= 2^N ). Users can choose one mode of charge among A and B by themselves,so the cost that the company charge from the great school is relative to the mode of charging by each user. The total cost equals to the sum of the cost of each pair of users.

Some definations:

For each pair of users i,j(1 <= i < j <= 2^N),first we find the LCA(Least Common Ancestor) of the two node named P,then let's consider the Donimated Leaves of P(the users assign to P). We define nA,nB denoted the number of users choose A and B to charge in these Donimated Leaves.

Charging is following the rule below:(in the rule,F(i,j) denotes the flux between i and j and will be given.)

Since the total cost is relative to the mode of charging,the users in the great Southern Moutain School hope to minimize the cost by changing the way of charging.However,the company has recorded the mode that each user choosed when they registered.So for each user i,if he/she wants to change the mode of charging,(change from mpde A to mode B,or change from mode B to mode A),he/she must pay $Ci to the company to modify the record.

Your task is:

Given the mode the users chosen when they registered,and Ci,decide the mode to charge of each user to minimize the total cost(the cost of changing mode + the sum of the cost of the Pairing Charging).

Input

T [The number of test cases]
N [N<=10]
D1 D1 D2 ... DM [M=2^N, Di=0 iff the mode user i chosen when he/she registerd is A and Di=1 otherwise.]
C1 C1 C2 ... CM [the cost of changing the mode of each user,0<=Ci<=500000]
F(1,2) F(1,3) ... F(1,M)
F(2,3) F(2,4) ... F(2,M)
...
F(M-2,M-1) F(M-2,M)
F(M-1,M)
[The table above is the flux table description,0<=F(i,j)<=500]
[other tests]

Output

TheMinCost
[other tests]

Example

Sample Input:
1
2
1 0 1 0
2 2 10 9
10 1 2
2 1
3

Sample Output:
8

Hints:
Change the mode of the first user from mode B to mode A.