描述

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

仙林校区一共有\(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