分数: 300 点
问题陈述
高桥是一名武术家。 有 N 武术家可以学习的动作,称为移动 1, 2, \ldots, N。 对于每个 1 \leq i \leq N,需要 T_i 学习 Move 的练习分钟数 i。 此外,在练习开始时,所有动作 A_{i,1}, A_{i,2}, \ldots, A_{i,K_i} 必须已经学会。 在此,可以保证 A_{i,j} < i 对于每个 1 \leq j \leq K_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.
示例输入 1
3 3 0 5 1 1 7 1 1
示例输出 1
10
这是高桥的一个可能的计划。
- 时间 0,开始练习移动 1 学习移动 1 时间 3.
- 然后,在某个时间 3,开始练习移动 3 学习移动 3 时间 10.
在这里,高桥花了 3+7=10 学习 Move 分钟 3,这是最快的。 注意他不需要学习Move 2 学习移动 3.
示例输入 2
5 1000000000 0 1000000000 0 1000000000 0 1000000000 0 1000000000 4 1 2 3 4
示例输出 2
5000000000
请注意,答案可能不适合 32位整数。