题目描述

小高是一名武术家。武术家可以学习 $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$ 所需的最少分钟数。

样例

3
3 0
5 1 1
7 1 1

10

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

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}$ 都是不同的。所有输入都是整数。

来源

• AtCoder ABC226C