在一个地图上有 $N\ (N \le 20)$ 个地窖，每个地窖中埋有一定数量的地雷（每个地窖的地雷均不超过 $300$ 个）。同时，给出地窖之间的连接路径。当地窖及其连接的数据给出之后，某人可以从任一处开始挖地雷，然后每次可以移动到一个编号比当前节点大且联通的节点去挖地雷，当无满足条件的节点时挖地雷工作结束。设计一个挖地雷的方案，使某人能挖到最多的地雷。

输入格式

有若干行。

第 $1$ 行只有一个数字，表示地窖的个数 $N$。

第 $2$ 行有 $N$ 个数，分别表示每个地窖中的地雷个数。

第 $3$ 行至第 $N+1$ 行表示地窖之间的连接情况：

第 $3$ 行有 $n-1$ 个数（$0$ 或 $1$），表示第一个地窖至第 $2$ 个、第 $3$ 个 $\dots$ 第 $n$ 个地窖有否路径连接。如第 $3$ 行为 $1\space 1\space 0\space 0\space 0\cdots 0$，则表示第 $1$ 个地窖至第 $2$ 个地窖有路径，至第 $3$ 个地窖有路径，至第 $4$ 个地窖、第 $5$ 个 $\dots$ 第 $n$ 个地窖没有路径。

第 $4$ 行有 $n-2$ 个数，表示第二个地窖至第 $3$ 个、第 $4$ 个 $\dots$ 第 $n$ 个地窖有否路径连接。

……

第 $n+1$ 行有 $1$ 个数，表示第 $n-1$ 个地窖至第 $n$ 个地窖有否路径连接。（为 $0$ 表示没有路径，为 $1$ 表示有路径）。

输出格式

第一行表示挖得最多地雷时的挖地雷的顺序，各地窖序号间以一个空格分隔，不得有多余的空格。

第二行只有一个数，表示能挖到的最多地雷数。

样例 1

输入：

5
10 8 4 7 6
1 1 1 0
0 0 0
1 1
1

输出：

1 3 4 5
27

提示与约束

【样例解释】 按样例输入，地窖 1 至 5 的地雷数依次为 10、8、4、7、6。允许向编号更大的相邻地窖移动，连接关系为：1→2、1→3、1→4、3→4、3→5、4→5。该文字说明由样例输入完整还原，替代原样例示意图。 最优路径为 $1 \to 3 \to 4 \to 5$，结果为 $27$。

【题目来源】

NOIP 1996 提高组第三题。

来源：Luogu_P2196。本站使用重新构建的测试数据。