← 返回题目列表

AtCoder · abc226_c

F. 武术家

中文机器翻译题面 查看原题

分数: 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位整数。