描述

仙林校区内开了一家新的轻食店！为了保证运送效率，他们决定雇佣计算机系的同学来送外卖。

仙林校区一共有$n$栋宿舍楼（编号$1$至$n$），宿舍楼之间有道路相连。为了叙述的方便，我们认为轻食店在$0$号宿舍楼。从$i$号宿舍楼到$j$号宿舍楼的最短路线需要骑$a_{ij}$分钟的电动车。值得一提的是，某些道路是上坡，某些道路是下坡，所以$a_{ij}$并不一定等于$a_{ji}$。

你目前在轻食店（0号宿舍楼），电动车上的外卖箱中有一些外卖，你需要规划一条时间最短的路线把外卖送完。由于轻食店的食物很好(jian)吃(fei)，所以订外卖的学生老早就在楼下等着了。当你到达一个宿舍楼之后，可以立即把所有该宿舍楼的外卖交付，交付的时间忽略不计。换言之，你送外卖的总用时等于你花在路上的时间之和。送完最后一份外卖后计时立刻停止，返回店铺的时间不计入总用时。

请输出最短的总用时和对应的路线。

输入输出格式

输入

第一行包括一个整数$n$。
第二行包括$n$个取值为$0$或$1$的整数。第$i$个整数为1表示你的电动车外卖箱中有第$i$栋宿舍楼的外卖，反之没有。数据保证本行至少有一个1。
接下来的$n+1$行，每行含有$n+1$个数，表示$a_{ij}$（注意$i,j$编号从$0$开始）。对于对角线上的元素（即$a_{ii}$），数值为零。这些数字在本题中没有意义。

输出

第一行输出一个整数，表示最短的总用时。
第二行输出若干整数（宿舍编号），表示送外卖的顺序。请注意，在本行输出整数的个数，应该等于输入数据的第二行中“$1$”的个数。

数据规模与说明

$1\leq n \leq 16$, $0\leq a_{ij}\leq 100000$.
如果有多条用时最少的路线，请输出字典序最大的那一条。即在用时最少的情况下，路线中第一个宿舍楼的编号尽可能大；在用时最少且第一个宿舍楼编号一样大的情况下，第二个宿舍楼的编号尽可能大，以此类推。
考虑到部分同学对最短路算法不熟悉，给定的$a_{ij}$已经是最短路径了。你不可能通过经由第三个宿舍楼构造出一条用时少于$a_{ij}$的路径。换言之，给定的$a_{ij}$矩阵满足三角不等式。

输入输出样例

输入

3
1 1 1 
0 7 4 1 
2 0 1 3 
5 4 0 6 
8 6 5 0 

输出

8
3 1 2 

来源

参照CodeVS 2800