Problem
エンタープライズ「Auto-2010」世界的に有名な自動車のエンジンを製造しています。エンジンは、1 から n までの番号が付けられた正確に n 個の部品で構成されており、番号 i の部品は pi 秒で作成されます。エンタープライズ「Auto-2010」の仕様一度に製造できるエンジン部品は 1 つだけです。一部のパーツは、他のパーツの組み立て済みセットを製造する必要があります。
「Auto-2010」総監督企業にとって野心的なタスクを設定する —品番1を最短で製作し展示会に出品。
部品間の製造順序の依存関係を考慮して、部品番号 1 を製造できる最短時間を見つけるプログラムを作成する必要があります。
入力
入力ファイルの最初の行には、数値 n (1≤ n ≤ 100000) — が含まれています。エンジンパーツの数々。 2 行目には、各部品の製造時間を秒単位で定義する n 個の正の整数 p
1、p
2、p
n が含まれています。各パーツの作成時間は 10
9 秒を超えません。
入力ファイルの次の n 行のそれぞれは、部品の生産の特徴を記述します。ここで、i 番目の行には、部品番号 i を製造するために必要な部品数 ki とその番号が含まれています。 i 行目に重複する部品番号はありません。すべての数値 k
i の合計は 200000 を超えません。
部品の製造には循環依存がないことが知られています。
インプリント
出力ファイルの最初の行には、部品番号 1 をできるだけ早く製造するのに必要な最小時間 (秒単位) と、このために製造する必要がある部品の数 k の 2 つの数値が含まれている必要があります。 2 行目では、スペースで区切られた k 個の数字を出力する必要があります —できるだけ早く部品番号 1 を製造するために、部品番号を製造する順序で示します。
<本体>
| 入力 |
出力 |
3
100 200 300
1 2
0
2 2 1
| 300 2
2 1
|
2
23
1 2
0 |
5 2
2 1
|
4
2 3 4 5
2 3 2
1 3
0
2 1 3
| 9 3
3 2 1
|