Maija works at a kindergarten. Today the kids are going on an excursion to the local forest and are getting lined up for the journey. The kids are numbered 1,2,\dots,n and Maija knows that the current rivalry level between kids i and j is r_{i, j}. To make the journey to the forest as safe and peaceful as possible, Maija is going to order the kids in such a way that the total sum of rivalries between adjacent kids is minimized. Help Maija find the minimal sum of rivalries.

Input

The first line contains a single integer n.

the i-th of next n following lines contains n integers r_{i, 1},\,r_{i, 2},\dots,\,r_{i, n}.

Output

Print the minimal sum of rivalries.

Constraints

• 1 \leq n \leq 16
• 0 \leq r_{i, j} \leq 10^9
• r_{i, j} = r_{j, i}

Example 1

Input:

4
0 5 1 4 
5 0 0 1 
1 0 2 2 
4 1 2 1

Output:

2

Explanation:

one way to order the kids is 1, 3, 2, 4

Example 2

Input:

10
549 646 792 87 979 640 264 618 359 671 
646 384 812 648 474 582 186 149 613 171 
792 812 529 20 799 143 775 612 437 210 
87 648 20 368 801 537 737 222 903 358 
979 474 799 801 461 945 456 617 698 129 
640 582 143 537 945 759 216 386 99 751 
264 186 775 737 456 216 569 944 60 315 
618 149 612 222 617 386 944 903 970 608 
359 613 437 903 698 99 60 970 667 364 
671 171 210 358 129 751 315 608 364 325

Output:

1257