题目描述

强哥立志成为一代武术大师，需要学习 $N$ 种独特的武术招式。每种招式都有特定的学习要求：

1. 学习时间：招式 $i$ 需要花费 $T_i$ 分钟专注练习
2. 前置条件：学习招式 $i$ 前，必须已经掌握 $K_i$个特定前置招式（$A_{i,1},...,A_{i,K_i}$）
3. 修行规则：
   • 每次只能专心练习一个招式
   • 一旦开始练习就必须完成
   • 初始时（时间 $0$）不会任何招式

现在强哥想知道，他最少需要多少分钟才能学会最强的第$N$ 招？

数据范围

• $1 \leq N \leq 2\times 10^5$
• $1 \leq T_ i \leq 10^9$
• $0 \leq K_i < i$
• $1\le 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₁ K₁ A₁₁ A₁₂ ... A₁K₁
T₂ K₂ A₂₁ A₂₂ ... A₂K₂
...
T_N K_N A_N₁ A_N₂ ... A_NK_N

输出格式

输出学会招式N所需的最少时间

输入样例1

3
3 0
5 1 1
7 1 1

输出样例1

10

输入样例2

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

输出样例2

5000000000