Network Charges

Time limit1sMemory limit256 MB

Summary

Choose plan A or B for each leaf of a perfect binary tree to minimize plan-change costs plus pairwise charges set by subtree majorities.

Level: Hard8 of 10
Topics: Graph, Tree, Dynamic programming
Solved: No attempts yet

Statement

Networking has become an essential part of the modern world. Each day, hundreds of millions of users use the web for education, research, entertainment, and more. The huge operating costs of networks cannot be ignored, so charging users appropriately is both necessary and reasonable.

City MY's NS high school has an educational network of this kind. The network has $2N$ users, labeled $1, 2, 3, \ldots, 2N$ . The network consists of routers and cables between the users. The users, routers, and cables form a perfect binary tree. Every leaf node is a user, every non-leaf node is a router, and every edge is a network cable.

The company uses a scheme called pairwise charging. A fee is charged for every pair of users $i$ and $j$ ( $1 \le i < j \le 2N$ ). Each user independently chooses plan A or plan B, so the charge depends on those choices. The total charge is the sum of all pairwise charges between different users.

Definitions:

Ancestor: The root node has no ancestors. The ancestors of a non-root node are its parent and the ancestors of its parent.
Containment of leaf nodes: A leaf node contains no leaf nodes. A non-leaf node contains the leaf nodes of its left child plus the leaf nodes of its right child.
Distance: The distance between two nodes is the number of edges on the shortest path connecting them.

For two users $i$ and $j$ ( $1 \le i < j \le 2N$ ), find the common ancestor router $P$ with the smallest distance to each user. Then count, among the leaf nodes (users) contained by $P$ , how many chose plan A and how many chose plan B. Call these counts $n_A$ and $n_B$ . The charge is then determined by the table below, where $F_{i,j}$ is the known data flow between $i$ and $j$ .

Plan of $i$	Plan of $j$	Relation between $n_A$ and $n_B$	Payment factor $k$	Actual charge (dollars)
A	A	$n_A < n_B$	2	$k \times F_{i,j}$
A	B		1
B	A		1
B	B		0
A	A	$n_A \ge n_B$	0
A	B		1
B	A		1
B	B		2

Users want to change their plans to minimize the total charge to the school. The company has recorded each user's plan at registration. If user $i$ changes plan (from A to B or from B to A), the school must pay $C_i$ dollars to update the record.

Given the initially registered plans and the costs $C_i$ , determine how the users should choose their plans so that the total fee paid to the company (plan change costs plus pairwise charges) is as small as possible.

Input

The first line contains one positive integer $N$ .

The second line contains $2N$ integers, the registered plans of users $1, 2, \ldots, 2N$ . Each number is 0 if the initial plan is A, or 1 if the initial plan is B.

The third line contains $2N$ integers $C_1, C_2, \ldots, C_{2N}$ , the cost in dollars for each user to change plans.

The next $2N-1$ lines contain the data flow table $F$ . The $(i+3)$ th line contains the $j$ -th integer $F_{i,j+i}$ ( $1 \le i < 2N$ , $1 \le j \le 2N-i$ ).

Output

Print a single integer, the minimum total amount in dollars that the school has to pay the company.

Constraints

$N \le 10$ , $0 \le F_{i,j} \le 500$ , $0 \le C_i \le 500\,000$ .

Examples1

Example 1
Input
```
2
1 0 1 0
2 2 10 9
10 1 2
2 1
3
```
Expected output
```
8
```