Description

Do you think team A is good or team B is good？

Given N people, you need to assign them to team A or team B so that each team happens to consist of N/2 people, making the competition value of these two teams the largest.

The total competitive value is the sum of the competitive value of each pair of people in different teams.

Ensure that N is an even number.

The equivalent equation is $ {\textstyle \sum_{i=1}^{N} \sum_{j=i+1}^{N}} v_{ij}$ if i-th person is not in the same team as j- th person else 0

Format

Input

The first line of input contains an integers N.

Following N lines each contains N space-separated integers $v_{ij}$ is the j-th value of the i-th line which indicates the competitive value of person i and person j.

$$\begin{matrix} N\,is\,even\\ 1\le N\le 28\\ 0\le v_{ij} \le 10^9\\ v_{ij}=v_{ji} \end{matrix} $$

Output

Output one line containing an integer representing the maximum possible total competitive value.

Samples

2
0 3
3 0

3

Hints

Suppose N = 4 and $v_{ij}=\begin{matrix} 0\,1\,2\,3\\1\,0\,5\,6\\2\,5\,0\,9\\3\,6\,9\,0 \end{matrix}$.Only 3 cases.

Case 1: team A={1, 2} , team B ={3, 4}, total competitive value is $v_{1,3}+v_{1,4}+v_{2,3}+v_{2,4}=2+3+5+6=16$.

Case 2: team A={1, 3} , team B ={2, 4}, total competitive value is $v_{1,2}+v_{1,4}+v_{2,3}+v_{2,4}=1+3+5+9=18$.

Case 3: team A={1, 4} , team B ={2, 3}, total competitive value is $v_{1,2}+v_{1,3}+v_{2,4}+v_{3,4}=1+2+6+9=18$.

So the maximum possible total competitive value is 18.