Type: Default 3000ms 512MiB

社团团建拼座位

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

社团团建要把 nn 位同学排成一排合影。第 ii 位同学和第 jj 位同学相邻时,会产生 ci,jc_{i,j} 点快乐值。

快乐值可以理解为:"他们终于找到一个能一起吐槽食堂的人"的程度。

你需要安排所有同学的顺序,使得相邻同学产生的快乐值总和最大。

形式化地,设排列为 p1,p2,…,pnp_1,p_2,\ldots,p_n,总快乐值为:

∑i=1n−1cpi,pi+1\sum_{i=1}^{n-1} c_{p_i,p_{i+1}}

请输出最大可能的总快乐值。

Format

Input

第一行一个整数 n(2≤n≤18)n(2 \le n \le 18)。

接下来 nn 行,每行 nn 个整数,第 ii 行第 jj 个数为 ci,j(0≤ci,j≤109)c_{i,j}(0 \le c_{i,j} \le 10^9)。

保证 ci,i=0c_{i,i}=0,且 ci,j=cj,ic_{i,j}=c_{j,i}。

Output

输出一行一个整数,表示最大总快乐值。

Samples

4
0 1 5 2
1 0 3 4
5 3 0 6
2 4 6 0
15

Note

样例说明:

一种最优排列为 1 3 4 21 \ 3 \ 4 \ 2,快乐值为 c1,3+c3,4+c4,2=5+6+4=15c_{1,3}+c_{3,4}+c_{4,2}=5+6+4=15。