{"trustable":true,"sections":[{"title":"説明","value":{"format":"MD","content":"地図上には $N\\ (N \\le 20)$ 個の地下室があり、それぞれの地下室には一定数の地雷が埋まっています。同時に、地下室間の接続経路が示されています。地下室とその接続のデータが与えられた後、誰かが任意の場所から地雷を掘り始め、示された接続に沿って掘り進むことができます(1つの経路のみを選択可能)接続がなくなると、地雷掘りは終了します。最大限の地雷を掘り出すための計画を設計してください。"}},{"title":"入力","value":{"format":"MD","content":"いくつかの行があります。\n\n第 $1$ 行には1つの数字があり、地下室の数 $N$ を示します。\n\n第 $2$ 行には $N$ 個の数字があり、それぞれの地下室にある地雷の数を示します。\n\n第 $3$ 行から第 $N+1$ 行まで、地下室間の接続状況を示します:\n\n第 $3$ 行には $n-1$ 個の数字($0$ または $1$)があり、最初の地下室から第 $2$ 個、第 $3$ 個 $\\dots$ 第 $n$ 個の地下室に接続があるかどうかを示します。例えば、第 $3$ 行が $11000\\cdots 0$ であれば、第 $1$ 個の地下室から第 $2$ 個の地下室に接続があり、第 $3$ 個の地下室に接続があり、第 $4$ 個の地下室、第 $5$ 個 $\\dots$ 第 $n$ 個の地下室には接続がないことを示します。\n\n第 $4$ 行には $n-2$ 個の数字があり、2番目の地下室から第 $3$ 個、第 $4$ 個 $\\dots$ 第 $n$ 個の地下室に接続があるかどうかを示します。\n\n……\n\n第 $n+1$ 行には $1$ 個の数字があり、第 $n-1$ 個の地下室から第 $n$ 個の地下室に接続があるかどうかを示します。($0$ は接続がないことを示し、$1$ は接続があることを示します。)"}},{"title":"出力","value":{"format":"MD","content":"最初の行には、最大の地雷を掘り出したときの掘り進む順序が示され、各地下室の番号は空白で区切られ、余分な空白があってはいけません。\n\n2行目には、掘り出せる最大の地雷の数を示す1つの数字があります。"}},{"title":"サンプル 1","value":{"format":"MD","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\n10 8 4 7 6\n1 1 1 0\n0 0 0\n1 1\n1\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 3 4 5\n27\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}},{"title":"ヒント","value":{"format":"MD","content":"**【問題の出典】**\n\nNOIP 1996 上級グループ 第3問"}}]}