/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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 を習得するのに必要な時間の最小値を出力せよ。
入力例 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
答えが 32 bit 整数に収まらないことがある事に注意してください。
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.