카트라이더 경험치

호준이는 자신을 포함해 $N$명의 친구와 함께 카트라이더 경주를 하려고 한다. 호준이는 경주하기 전에 카트라이더 내부 보상 시스템 정보를 입수했다.

호준이를 포함해 호준이의 친구들은 $1$부터 $N$까지 번호가 매겨져 있고, 내부 보상시스템은 $N\times N$ 크기의 경험치 테이블로 구성되어 있다. 경험치 테이블 $M(i, j)$에는 $i$가 $j$보다 먼저 골인했을 때 받을 수 있는 경험치가 적혀있다. 단, 자신이 자신보다 먼저 골인하는 경우는 없기 때문에 $M(i, i)$에는 $0$이 적혀있다.

예를 들어 호준이를 포함한 $3$명의 친구가 경주를 하고, $2$ → $3$ → $1$ 순서로 골인한다면 $1$은 아무 경험치를 못 받고, $2$는 $M(2, 1) + M(2, 3)$의 경험치를 받고, $3$은 $M(3, 1)$의 경험치를 받는다.

호준이는 월등한 실력으로 $1$등을 할 수 있었지만, 친구들을 배려해 결승점에 들어올 순서를 미리 정해서 모두가 얻는 경험치 합을 최대화하려고 한다. 호준이를 도와 모두가 얻는 경험치 합의 최댓값을 구해주자.

입력 형식

첫 줄에 호준이를 포함한 친구의 수 $N$이 입력으로 주어진다. ($2 \le N \le 15$)

$i+1$번째 줄에 $N$개의 자연수가 공백으로 구분되어 주어지는데, $j$번째 정수는 경험치 테이블의 정보 $M(i, j)$를 의미한다. ($1 \le i, j \le N$; $0 \le M(i, j) \le 10\,000\,000$)

출력 형식

순서를 잘 정했을 때 얻을 수 있는 경험치 합의 최댓값을 출력하라.

예제

3
0 10 2
3 0 20
40 31 0

81

채점 방식

입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.

해설