Network Saboteur#2647
A university network consists of computers. System administrators collected information about the traffic between nodes and divided the network into two subnetworks in order to minimize the traffic between them.
After being expelled, a disgruntled computer science student named Vasya decided to take revenge. He hacked into the university network and tried to reassign computers in such a way as to maximize the traffic between the two subnetworks.
Unfortunately, he realized that finding such a worst-case division is one of those problems he could not solve as a student. Therefore, he turns to you, a more successful computer science student, for help.
The traffic data is provided as a matrix , where C_{ij} is the amount of data sent between the -th and -th nodes (C_{ij} = C_{ji}, C_{ii} = 0). The goal is to divide the network nodes into two disjoint subsets and so as to maximize the sum of the traffic between them.
The first line of the input file contains the number of nodes (2 \leq N \leq 20). The following lines, each containing space-separated integers, represent the traffic matrix (0 \leq C_{ij} \leq 10000).
The output file must contain a single integer: the maximum traffic between the subnetworks.
Example 1