题目描述

在一个地下矿场中有 $N\ (N \le 20)$ 个矿洞,每个矿洞中藏有一定数量的宝石（每个矿洞的宝石均不超过 $300$ 个）。同时,矿洞之间由若干条通道连接。当地矿洞及其通道的数据给出之后,探险者可以从任一处开始挖掘,然后每次可以移动到一个编号比当前矿洞大且有通道连接的矿洞去挖掘,当无满足条件的矿洞时挖掘工作结束。设计一个挖掘方案,使探险者能挖到最多的宝石。

输入格式

有若干行。

第 $1$ 行只有一个数字,表示矿洞的个数 $N$。

第 $2$ 行有 $N$ 个数,分别表示每个矿洞中的宝石个数。

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

第 $3$ 行有 $n-1$ 个数（$0$ 或 $1$）,表示第 $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$ 个数,表示第 $2$ 个矿洞至第 $3$ 个、第 $4$ 个 $\dots$ 第 $n$ 个矿洞是否有通道连接。

……

第 $n+1$ 行有 $1$ 个数,表示第 $n-1$ 个矿洞至第 $n$ 个矿洞是否有通道连接。（为 $0$ 表示没有通道,为 $1$ 表示有通道）。

输出格式

第一行表示挖得最多宝石时的挖掘顺序,各矿洞序号间以一个空格分隔,不得有多余的空格。

第二行只有一个数,表示能挖到的最多宝石数。

样例

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

1 3 4 5
27

提示

样例解释

最优路径为 $1 \to 3 \to 4 \to 5$,结果为 $27$。