题目描述

Takahashi 是一名武术家。有 $N$ 个招式可以学习，分别称为招式 $1$、$2$、$\\ldots$、$N$。对于每个 $1 \\leq i \\leq N$，需要练习 $T_i$ 分钟才能学会招式 $i$。此外，在开始练习之前，必须已经学会了所有招式 $A_{i,1}$、$A_{i,2}$、$\\ldots$、$A_{i,K_i}$。这里保证对于每个 $1 \\leq j \\leq K_i$，都有 $A_{i,j} < i$。

Takahashi 在时刻 $0$ 还没有学会任何招式。他不能同时练习多个招式，也不能停止已经开始的练习。找出 Takahashi 学会招式 $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}$

输出

打印 Takahashi 学会招式 $N$ 所需的最少分钟数。

示例输入 1

3
3 0
5 1 1
7 1 1

示例输出 1

10

以下是 Takahashi 的一个可能计划。

• 在时刻 $0$，开始练习招式 $1$，在时刻 $3$ 学会招式 $1$。
• 然后，在时刻 $3$ 开始练习招式 $3$，在时刻 $10$ 学会招式 $3$。

这里，Takahashi 花费了 $3+7=10$ 分钟学会招式 $3$，这是最快的方式。请注意，他学会招式 $3$ 时不需要学会招式 $2$。

示例输入 2

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

示例输出 2

5000000000

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