Network Saboteur

Time limit1sMemory limit128 MB

Summary

Split N nodes (N <= 20) into two sets A and B so the total weight of edges crossing between them is maximized.

Level: Medium5 of 10
Topics: Brute force, Backtracking, Implementation
Solved: No attempts yet

Problem

A university network consists of $N$ computers. The system administrators measured the traffic between every pair of nodes and split the network into two subnetworks so that the traffic flowing between the two parts is as small as possible.

A disgruntled student, Vasya, who was expelled from the university, wants to do the opposite. He has taken control of the network and wants to reassign the computers so that the traffic between the two subnetworks is as large as possible. Computing this worst-case split is a problem he cannot solve, so he asks you for help.

The traffic is given as a matrix $C$ , where $C_{ij}$ is the amount of data exchanged between node $i$ and node $j$ . The matrix is symmetric ( $C_{ij} = C_{ji}$ ) and has no self-traffic ( $C_{ii} = 0$ ). Partition the $N$ nodes into two disjoint sets $A$ and $B$ so as to maximize

$\sum_{i \in A,\; j \in B} C_{ij}.$

Input

The first line contains the number of nodes $N$ ( $2 \le N \le 20$ ).

Each of the following $N$ lines contains $N$ space-separated integers; the $j$ -th integer on the $i$ -th line is $C_{ij}$ ( $0 \le C_{ij} \le 10000$ ). The matrix is symmetric with a zero diagonal.

Output

Print a single integer — the maximum possible traffic between the two subnetworks.

Examples4

Example 1
Input
```
3
0 50 30
50 0 40
30 40 0
```
Expected output
```
90
```
Example 2
Input
```
2
0 100
100 0
```
Expected output
```
100
```
Example 3
Input
```
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
```
Expected output
```
4
```

Example 4

Input

Expected output