Description

社团团建要把 $n$ 位同学排成一排合影。第 $i$ 位同学和第 $j$ 位同学相邻时，会产生 $c_{i,j}$ 点快乐值。

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

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

形式化地，设排列为 $p_1,p_2,\ldots,p_n$，总快乐值为：

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

Format

Input

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

接下来 $n$ 行，每行 $n$ 个整数，第 $i$ 行第 $j$ 个数为 $c_{i,j}(0 \le c_{i,j} \le 10^9)$。

保证 $c_{i,i}=0$，且 $c_{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 \ 2$，快乐值为 $c_{1,3}+c_{3,4}+c_{4,2}=5+6+4=15$。