题目描述

给定一个有向的完全图（任意两点之间都有边称之为完全图）。这个图有 $n$ 个点，其中第 $i$ 个点到第 $j$ 个点的边的长度为 $a_{i,j}$，请为这张图找一个圈，这个圈从第 $1$ 个点出发，不重复不遗漏地经过每个点，最后回到起点，则路径之和最长是多少。

输入格式

• 第一行：单个整数表示 $n$
• 第二行到第 $n+1$ 行：第 $i+1$ 行有 $n$ 个整数表示 $a_{i,1}$ 到 $a_{i,n}$

输出格式

• 单个整数表示答案

3
0 5 6
7 0 5
9 3 0

19

样例解释 1

3-->1-->2-->3 9 + 5 + 5 = 19

数据范围

• $30\%$ 的数据，$1\leq n\leq 5$
• $60\%$ 的数据，$1\leq n\leq 12$
• $100\%$ 的数据，$1\leq n\leq 20$
• $0\leq a_{i,j}\leq 10,000,000$
• $a_{i,i}=0$