当前没有测试数据。

C - 武术家

得分：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$时还没有学会任何招式。 他不能同时练习多个招式，也不能停止他已经开始的练习。 求高桥学会招式$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+7=10$分钟学会招式$3$，这是可能的最快方式。 注意他不需要先学会招式$2$才能学会招式$3$。

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

5000000000

请注意，答案可能不适合$32$位整数。