Description

The network has become an indispensable part of today’s world. Hundreds of millions of people use the network every day for learning, research, entertainment, and more. However, it is important to note that the network itself has huge operating costs. Therefore, it is necessary and reasonable to charge users appropriately.

NS Middle School in MY City has such an educational network. There are $2^N$ users in the network, numbered $1, 2, 3, \cdots, 2^N$. These users are connected by router nodes and network cables. The users, router nodes, and network cables together form a full binary tree. Every leaf node of the tree is a user, every non-leaf node (gray) is a router node, and every edge is a network cable (see the figure; the numbers in user nodes are their IDs).

MY Network Company uses an unusual pricing model called “paired charging.” That is, fees are charged for every pair of users $i, j$ with $1 \leq i < j \leq 2^N$. Since each user can independently choose one of the two payment plans A or B, the fee the company charges the school depends on each user’s plan. The total fee equals the sum of the fees generated by all pairs of distinct users.

For convenience, we first define some concepts on this network tree:

• Ancestor: The root node has no ancestors. For a non-root node, its ancestors include its parent and all ancestors of its parent.
• Covered leaf nodes: A leaf node covers no leaf nodes. A non-leaf node covers the leaf nodes covered by its left child and the leaf nodes covered by its right child.
• Distance: The number of edges on a shortest path connecting two nodes in the tree.

For any two users $i, j$ with $1 \leq i < j \leq 2^N$, first find their nearest common ancestor (LCA) in the tree: router node $P$. Then, among the leaf nodes (i.e., users) covered by $P$, count how many chose plan A and how many chose plan B, denoted $n_A$ and $n_B$, respectively. Next, the fee is charged according to Article X, Section Y, Clause Z of the Network Management Regulations (see the table below), where $F_{i,j}$ is the traffic between $i$ and $j$, and $F_{i,j}$ is known.

Since the final amount paid depends on the choice of payment plans, users at NS Middle School hope to change their plans to reduce the total payment. However, since the network company has recorded the plan each user chose at registration, user $i$ must pay $C_i$ yuan to the company to modify the record (switch plan A to B or B to A).

Now the problem: given each user’s initial plan and the values $C_i$, determine how these users should choose their plans to minimize the total fee NS Middle School pays to the network company (switching fees + paired charging fees).

Input Format

The first line contains a positive integer $N$.

The second line contains $2^N$ integers, giving the initial plan of users $1, 2, \cdots, 2^N$. If a number is 0, the corresponding user’s initial plan is A; otherwise the number is 1, meaning plan B.

The third line contains $2^N$ integers, the switching fee for each user, namely $C_1, C_2, \cdots, C_{2^N}$.

The next $2^N - 1$ lines describe the traffic table $F$ between every pair of users. Specifically, in the overall line $i + 3$, the integer in column $j$ equals $F_{i, j + i}$, for $1 \leq i < 2^N$ and $1 \leq j \leq 2^N - i$.

See the problem statement for the meaning of all variables.

Output Format

Output a single integer: the minimum total fee (in yuan) that NS Middle School pays to the network company.

2
1 0 1 0
2 2 10 9
10 1 2
2 1
3

8

Hint

Sample Explanation: Changing user $1$ from plan B to plan A yields the minimum total payment.

Constraints:

• In $40\%$ of the testdata, $N \leq 4$.
• In $80\%$ of the testdata, $N \leq 7$.
• In $100\%$ of the testdata, $N \leq 10$, $0 \leq F_{i,j} \leq 500$, $0 \leq C_i \leq 500000$.

Translated by ChatGPT 5