题目描述

高橋君は武術家です。 武術家の覚えられる技は $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$ を習得するのに必要な時間の最小値を求めてください。

输入格式

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

$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

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

5000000000

提示

制約

• $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}$ はすべて異なる。
• 入力は全て整数である。

Sample Explanation 1

例えば高橋君は次のように行動することができます。 - 高橋君は時刻 $0$ に技 $1$ の修練を開始し、時刻 $3$ に技 $1$ を習得します。 - その後、時刻 $3$ に技 $3$ の修練を開始し、時刻 $10$ に技 $3$ を習得します。 このときが最短で、高橋君が技 $3$ を習得するのに必要な時間は $3+7=10$ となります。 技 $3$ の習得のためには、技 $2$ を習得する必要はありません。

Sample Explanation 2

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