配点 : $300$ 点

問題文

高橋君は武術家です。 武術家の覚えられる技は $N$ 個あり、技 $1$, $2$, $\ldots$, $N$ と名前がついています。 $1 \leq i \leq N$ について、技 $i$ を習得するには時間 $T_i$ の修練が必要で、 さらに、修練の開始時点で技 $A_{i,1}$, $A_{i,2}$, $\ldots$, $A_{i,K_i}$ をすでに習得している必要があります。 ここで、$1 \leq j \leq K_i$ について、$A_{i,j} < i$ であることが保証されます。

高橋君は時刻 $0$ の時点で技を $1$ つも覚えていません。 高橋君は同時に $1$ つの技に対する修練しかできず、また、一度始めた修練を途中でやめることもできません。 高橋君が技 $N$ を習得するのに必要な時間の最小値を求めてください。

制約

• $1 \leq N \leq 2\times 10^5$
• $1 \leq T_i \leq 10^9$
• $0 \leq K_i < i$
• $1 \leq A_{i,j} < i$
• $\sum_{i=1}^N K_i \leq 2\times 10^5$
• $A_{i,1}$, $A_{i,2}$, $\ldots$, $A_{i,K_i}$ はすべて異なる。
• 入力は全て整数である。

入力

入力は以下の形式で標準入力から与えられる。

$N$

$T_1$ $K_1$ $A_{1,1}$ $A_{1,2}$ $\ldots$ $A_{1,K_1}$

$T_2$ $K_2$ $A_{2,1}$ $A_{2,2}$ $\ldots$ $A_{2,K_2}$

$\vdots$

$T_N$ $K_N$ $A_{N,1}$ $A_{N,2}$ $\ldots$ $A_{N,K_N}$

出力

技 $N$ を習得するのに必要な時間の最小値を出力せよ。

3
3 0
5 1 1
7 1 1

10

例えば高橋君は次のように行動することができます。

• 高橋君は時刻 $0$ に技 $1$ の修練を開始し、時刻 $3$ に技 $1$ を習得します。
• その後、時刻 $3$ に技 $3$ の修練を開始し、時刻 $10$ に技 $3$ を習得します。

このときが最短で、高橋君が技 $3$ を習得するのに必要な時間は $3+7=10$ となります。 技 $3$ の習得のためには、技 $2$ を習得する必要はありません。

5
1000000000 0
1000000000 0
1000000000 0
1000000000 0
1000000000 4 1 2 3 4

5000000000

答えが $32$ bit 整数に収まらないことがある事に注意してください。