4240: Martial artist

# Martial artist ### 内存 1024MB ### 时间 2S ## 题目描述 小高是一名武术家。武术家可以学习 $N$ 种动作，称为动作$1、2、...、N$。对于每个$1 ≤ i ≤ N$，学习动作 $i$ 需要 $T_i$ 分钟的练习。此外，在开始练习之前，必须已经学会了动作$A_{i,1}、A_{i,2}、...、A_{i,K_i}$。这里保证对于每个$1 ≤ j ≤ K_i$，都有$A_{i,j} < i$。 小高在时间 $0$ 时还没有学会任何动作。他不能同时练习多个动作，也不能中断已经开始的练习。请找出小高学会动作 $N$ 所需的最少分钟数。 ## 输入格式 输入按以下格式从标准输入给出： $N$ $T_1$ $K_1$ $A_{1,1 }$ $A_{1,2 }\cdots$ $A_{1,K_1}$ $T_2$ $K_2$ $A_{2,1 }$ $A_{2,2 }\cdots$ $A_{2,K_2}$ $\vdots$ $T_N$ $K_N$ $A_{N,1 }$ $A_{N,2 }\cdots$ $A_{N,K_N}$ ## 输出格式 输出小高学会动作 $N$ 所需的最少分钟数。 ## 输入输出样例 ### 输入样例1 ``` 3 3 0 5 1 1 7 1 1 ``` ### 输出样例1 ``` 10 ``` ### 输入样例2 ``` 5 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 4 1 2 3 4 ``` ### 输出样例2 ``` 5000000000 ``` ## 数据范围与提示 【样例1说明】 以下是小高可能的一种计划： - 在时间 0，开始练习动作 1，在时间 3 学会动作 1。 - 然后在时间 3，开始练习动作 3，在时间 10 学会动作 3。 在这里，小高花费了 3+7=10 分钟学会动作 3，这是最快的可能方案。注意他不需要学习动作 2 就可以学习动作 3。 【样例2说明】 注意答案可能不适合 32 位整数。 【数据范围】 $1 ≤ N ≤ 2×10^5, 1 ≤ T_i ≤ 10^9, 0 ≤ K_i < i, 1 ≤ A_{i,j} < i, \sum_{i=1}^N K_i \leq 2\times 10^5$, $A_{i,1}、A_{i,2}、...、A_{i,K_i}$ 都是不同的。所有输入都是整数。 ## 题目来源 ABC226C