武术家

题目描述

高桥君是一位武术家。

武术家可以学会 $N$ 种招式,称为招式 $1$、招式 $2$、……、招式 $N$。

对于每个 $1 \le i \le N$,学会招式 $i$ 需要 $T_i$ 分钟的练习。此外,在该练习开始前,招式 $A_{i,1}$、$A_{i,2}$、……、$A_{i,K_i}$ 必须已经全部学会。

这里,保证对每个 $1 \le j \le K_i$,都有 $A_{i,j} \lt i$。

在时刻 $0$,高桥君还没有学会任何招式。他不能同时练习多个招式,也不能中途停止已经开始练习的招式。

求高桥君学会招式 $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

以下是高桥君的一种可行方案。

在时刻 $0$ 开始练习招式 $1$,在时刻 $3$ 学会招式 $1$。

然后,在时刻 $3$ 开始练习招式 $3$,在时刻 $10$ 学会招式 $3$。

这里,高桥君用了 $3+7=10$ 分钟学会招式 $3$,这是最快的方法。

注意,学会招式 $3$ 不需要学会招式 $2$。

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

5000000000

注意,答案可能超出 $32$ 位整数能表示的范围。

数据范围

• $1 \le N \le 2 \times 10^5$
• $1 \le T_i \le 10^9$
• $0 \le K_i \lt i$
• $1 \le A_{i,j} \lt i$
• $\sum_{i=1}^N K_i \le 2 \times 10^5$
• $A_{i,1}$、$A_{i,2}$、……、$A_{i,K_i}$ 互不相同。
• 输入中的所有值均为整数。