AT_abc226_c [ABC226C] Martial artist

题目描述

高桥君是一位武术大师，他可以学习 $N$ 种技能，这些技能分别标号为 $1, 2, \ldots, N$。要学习每个技能 $i$，他需要花费 $T_i$ 时间进行修炼，并且在开始时必须已掌握技能 $A_{i,1}, A_{i,2}, \ldots, A_{i,K_i}$。这里保证了，每个前置技能的编号小于当前技能编号，即 $A_{i,j} < 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$ 所需的最短时间。

输入输出样例 #1

输入 #1

3
3 0
5 1 1
7 1 1

输出 #1

10

输入输出样例 #2

输入 #2

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

输出 #2

5000000000

说明/提示

• $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}$ 全部互不相同。
• 所有输入均为整数。

示例 1

高桥君可以采取这样的修习顺序：

• 他在时刻 $0$ 开始学习技能 $1$，到时刻 $3$ 时掌握此技能。
• 然后，从时刻 $3$ 开始修炼技能 $3$，到时刻 $10$ 时学会此技能。 这样一来，高桥君学习到技能 $3$ 的最短时间为 $3 + 7 = 10$。在这过程中，他不需要掌握技能 $2$。

提示 2

请注意，答案可能超过 $32$ 位整数的范围。

本翻译由 AI 自动生成