Problem Statement

Mr. A is a manager at an idol agency.
This idol agency has n idols registered (n is a multiple of 2).
It has been decided that all of them will be put into groups of two (pairs) and promoted.
Every two people have a compatibility, and the compatibility level of the two directly becomes the idols' popularity.
Letting the two people be a, b and letting f be the function that gives the compatibility level, we have f(a,b)=f(b,a).
The compatibility levels for all combinations of two people are given as an n*n table. (f(a,a) is impossible, so -1 is given.)
Find the total popularity when pairs are formed so that the sum of the popularity of all pairs is maximized.
(Hint: The intended solution runs the heaviest test data, n=24, reliably within one second in Ruby, and within 0.1 seconds in C++.)

Input

$n$
$F11$ $\dots$ $F1n$
$\dots$
$Fn1$ $\dots$ $Fnn$

1<n<=24

0<=fij<=1000

The number of idols n is given on the first line. The following n lines give the compatibility table of the idols as an n*n table.
The first row is idol 1, the second row is idol 2, ..., and the n-th row is idol N.
The first column is idol 1, the second column is idol 2, ..., and the n-th column is idol N.
For example, to see the compatibility of idol 1 and idol 3, look at row 1, column 3 or row 3, column 1. To see the compatibility of idol 2 and idol 7, look at row 2, column 7 or row 7, column 2. Print on one line $S$, the popularity when pairs are formed so that the total popularity of all pairs is maximized.

Output

S Print a newline at the end.

Sample

4
-1 16 15 38
16 -1 22 17
15 22 -1 19
38 17 19 -1

60

6
-1 14 29 35 39 8
14 -1 35 41 34 3
29 35 -1 14 21 21
35 41 14 -1 12 42
39 34 21 12 -1 28
8 3 21 42 28 -1

116