Description

On a map there are $N$ ($N \le 20$) cellars, each containing a certain number of mines. The connections between cellars are given. After the data of the cellars and their connections are provided, a person can start digging mines from any cellar. Each time, they may move to a connected cellar whose index is strictly larger than the current node’s index to dig mines. The digging ends when there is no node that satisfies the condition. Design a digging plan so that the person can collect the maximum number of mines.

Input Format

Multiple lines.

The first line contains a single integer, the number of cellars $N$.

The second line contains $N$ integers, representing the number of mines in each cellar.

Lines $3$ to $N+1$ describe the connections between cellars:

• Line $3$ has $N-1$ numbers ($0$ or $1$), indicating whether there is a path from the first cellar to the $2$-nd, $3$-rd, …, $N$-th cellar. For example, if line $3$ is $1\ 1\ 0\ 0\ 0 \cdots 0$, it means there is a path from cellar $1$ to cellar $2$, a path from cellar $1$ to cellar $3$, and no path from cellar $1$ to cellar $4$, cellar $5$, …, cellar $N$.
• Line $4$ has $N-2$ numbers, indicating whether there is a path from the second cellar to the $3$-rd, $4$-th, …, $N$-th cellar.
• …
• Line $N+1$ has $1$ number, indicating whether there is a path from the $(N-1)$-th cellar to the $N$-th cellar (where $0$ means no path and $1$ means there is a path).

Output Format

The first line prints the digging order when the maximum number of mines is collected. The indices of the cellars are separated by a single space, with no extra spaces.

The second line contains a single integer, the maximum number of mines that can be collected.

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

1 3 4 5
27

Hint

[Sample Explanation] The optimal path is $1 \to 3 \to 4 \to 5$, and the result is $27$.

[Source] NOIP 1996 Senior, Problem 3.

Translated by ChatGPT 5