巨大建築 (paizaランク B 相当)

問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！

問題

下記の問題をプログラミングしてみよう！

世界最大規模の建築物をつくろうと考えている paiza 君は、どうすれば最小費用で完成できるか考えています。
paiza 国では、どんな建築物・建築部品も依頼して購入することができますが、それぞれの建築物・建築部品を作成するために必要な建築部品を購入・作成して、それらを用いて自分で作成することもできます。
paiza 君が考えている建築物や、必要な建築部品についての情報が与えられるので、この建築物を完成させるために必要な費用の最小値を求めてください。

入力される値

n
RECIPE_1
RECIPE_2
...
RECIPE_n

・ 1 行目に、建築物・建築部品の総数を表す整数 n が与えられます。
・続く n 行では、i 番目の建築物・建築部品についての情報 RECIPE_i が与えられます。(1 ≦ i ≦ n)
・特に、RECIPE_1 は paiza 君が作る建築物についての情報、RECIPE_2 から RECIPE_n まではそれぞれの建築部品についての情報を表します。

建築物・建築部品についての情報 RECIPE は、以下の形式で与えられます。

cost num part_1 part_2 ... part_num

・建築物・建築部品を購入するために必要な費用 cost と、その建築物・建築部品を自分で作成するために必要な建築部品の数 num が半角スペース区切りで与えられ、その後、必要な建築部品の番号を表す整数 part_1, part_2, ..., part_num が半角スペース区切りで与えられます。ただし、その建築物・建築部品を作成する方法が無い場合は、num が 0 になることに注意してください。その場合は、購入することでしか手に入れることはできません。

入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。標準入力からの値取得方法はこちらをご確認ください

期待する出力: 答えの整数を 1 行に出力してください。

また、末尾に改行を入れ、余計な文字を含んではいけません。

条件: すべてのテストケースにおいて、以下の条件をみたします。

・入力はすべて整数
・ 2 ≦ n ≦ 100,000 = 10^5
・ 1 ≦ cost ≦ 10^9
・各 RECIPE_i において 0 ≦ num < n - i
・各 RECIPE_i において i < part_1 < part_2 < ... < part_num ≦ n
・与えられる構造は根付き木をなす
・ RECIPE_1 は paiza 君が考えている建築物についての情報である

入力例1: 4
120 2 2 3
50 1 4
70 0
40 0

出力例1: 110

問題一覧へ戻る