Contest Duration: - (local time) (100 minutes) Back to Home
C - Martial artist /

Time Limit: 2 sec / Memory Limit: 1024 MB

### 制約

• 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 を習得するのに必要な時間の最小値を出力せよ。

### 入力例 1

3
3 0
5 1 1
7 1 1


### 出力例 1

10


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

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

### 入力例 2

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


### 出力例 2

5000000000


Score : 300 points

### Problem Statement

Takahashi is a martial artist. There are N moves that a martial artist can learn, called Move 1, 2, \ldots, N. For each 1 \leq i \leq N, it takes T_i minutes of practice to learn Move i. Additionally, at the beginning of that practice, all of the Moves A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} must be already learned. Here, it is guaranteed that A_{i,j} < i for each 1 \leq j \leq K_i.

Takahashi has not learned any move at time 0. He cannot practice for more than one move simultaneously, nor can he stop a practice he has already started. Find the minimum number of minutes needed for Takahashi to learn Move N.

### Constraints

• 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} are all distinct.
• All values in input are integers.

### Input

Input is given from Standard Input in the following format:

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}


### Output

Print the minimum number of minutes needed for Takahashi to learn Move N.

### Sample Input 1

3
3 0
5 1 1
7 1 1


### Sample Output 1

10


Here is one possible plan for Takahashi.

• At time 0, start practicing for Move 1 to learn Move 1 at time 3.
• Then, at time 3, start practicing for Move 3 to learn Move 3 at time 10.

Here, Takahashi spends 3+7=10 minutes to learn Move 3, which is the fastest possible. Note that he does not need to learn Move 2 to learn Move 3.

### Sample Input 2

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


### Sample Output 2

5000000000


Note that the answer may not fit into a 32-bit integer.