4225: 完全回路(road)

给出一个完全的有向图，求一条除起点外（最终回到起点）经过且仅经过每个顶点一次的路 径，使得经过的权值最大。

输入

第一行 输入一个正整数n。

接下来一个 n*n 的矩阵， 第 i 行第 j 列表示从点 i 到点 j 的边的长度。

输出

共 n+2 行 第一行 最大的权值

接下来 n+1 行 输出路径 若存在多条路径 输出字典序列最小的。

样例输入

3

0 10 30

30 0 30

50 30 0

样例输出

90

1

2

3

1

规模

N<=15