The network has become an indispensable part of the modern world. Every day, hundreds of millions of people use the network for learning, research, entertainment, and other activities. However, one point that cannot be ignored is that the network itself has huge operating costs. Therefore, it is necessary and reasonable to charge users for using the network.
NS Middle School in MY City has such an educational network. There are $2^N$ users in the network, numbered $1, 2, 3, \dots, 2^N$. These users are connected by routing points and network cables. Users, routing points, and network cables form a full binary tree structure. Every leaf node in the tree is a user, every non-leaf node (gray) is a routing point, and every edge is a network cable (see the figure below, the numbers in the user nodes are their IDs).
The network charging method of the MY network company is quite unique, called "Pairwise Charging." That is, for every two users $i, j$ ($1 \le i < j \le 2^N$), a fee is charged. Since users can choose one of two payment methods, A or B, the fee charged by the network company to the school depends on the payment method of each user. This fee is equal to the sum of the fees generated by every pair of different users.
For the sake of description, we first define some concepts on this network tree: Ancestor: The root node has no ancestors. The ancestors of a non-root node include its parent and the ancestors of its parent. Governed Leaf Nodes: A leaf node does not govern any leaf nodes. A non-leaf node governs the leaf nodes governed by its left child and the leaf nodes governed by its right child. *Distance: The number of edges in the shortest path connecting two points in the tree.
For any two users $i, j$ ($1 \le i < j \le 2^N$), first find their lowest common ancestor in the tree: a routing point $P$. Then, observe the number of people who chose payment method A and B among the leaf nodes (i.e., users) governed by $P$, denoted as $n_A$ and $n_B$ respectively. Then, according to the network management regulations, the fee is charged (as shown in the table below), where $F_{i,j}$ is the traffic between $i$ and $j$, which is a known quantity.
| $i$ Payment Method | $j$ Payment Method | $n_A$ vs $n_B$ Relationship | Payment Coefficient $k$ | Actual Fee |
|---|---|---|---|---|
| A | A | $n_A < n_B$ | 2 | $k \times F_{i,j}$ |
| A | B | $n_A < n_B$ | 1 | $k \times F_{i,j}$ |
| B | A | $n_A < n_B$ | 1 | $k \times F_{i,j}$ |
| B | B | $n_A < n_B$ | 0 | $k \times F_{i,j}$ |
| A | A | $n_A \ge n_B$ | 0 | $k \times F_{i,j}$ |
| A | B | $n_A \ge n_B$ | 1 | $k \times F_{i,j}$ |
| B | A | $n_A \ge n_B$ | 1 | $k \times F_{i,j}$ |
| B | B | $n_A \ge n_B$ | 2 | $k \times F_{i,j}$ |
Since the final fee depends on the payment method, users at NS Middle School hope to change their payment methods to reduce the total fee. However, because the network company has already recorded the payment method chosen by each user at registration, for user $i$, if he/she wants to change the payment method (from A to B or from B to A), he/she must pay $C_i$ yuan to the network company to modify the file (modify the payment method record).
The problem now is, given the payment method chosen by each user at registration and $C_i$, find how these users should choose their payment methods so that the total fee paid by NS Middle School to the network company is minimized (cost of changing payment methods + cost of pairwise charging).
Input
The first line of the input file contains a positive integer $N$. The second line contains $2^N$ integers, representing the payment methods of users $1, 2, \dots, 2^N$ at registration. If a number is $0$, it means the initial payment method of the corresponding user is A; otherwise, the number is $1$, indicating the payment method is B. The third line contains $2^N$ integers, representing the cost for each user to change their payment method, which are $C_1, C_2, \dots, C_M$ ($M=2^N$). The following $2^N-1$ lines describe the traffic table $F$ between the given pairs of users. The integer in the $j$-th column of the $(i+3)$-th line is $F_{i, j+i}$ ($1 \le i < 2^N$, $1 \le j \le 2^N - i$).
Output
Your program only needs to output a single integer to the output file, representing the minimum total fee paid by NS Middle School to the network company (unit: yuan).
Examples
Input 1
2 1 0 1 0 2 2 10 9 10 1 2 2 1 3
Output 1
8
Note 1
Changing the payment method of user 1 from B to A minimizes the fee paid by NS Middle School to the network company.