题目描述

小高是一名武术家。武术家可以学习 $N$ 种动作，称为动作 $1、2、...、N$。对于每个 $1≤i≤N$，学习动作 $i$ 需要 $T_i$ 分钟的练习。此外，在开始练习之前，必须已经学会了动作 $A_{i,1},A_{i,2},\cdots,A_{i,K}$。这里保证对于每个 $1≤j≤K_i$，都有 $A_{i,j}<i$。

小高在时间 $0$ 时还没有学会任何动作。他不能同时练习多个动作，也不能中断已经开始的练习。请找出小高学会动作 $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 解释

以下是小高可能的一种计划：

• 在时间 0，开始练习动作 1，在时间 3 学会动作 1。
• 然后在时间 3，开始练习动作 3，在时间 10 学会动作 3。

在这里，小高花费了 3+7=10 分钟学会动作 3，这是最快的可能方案。注意他不需要学习动作 2 就可以学习动作 3。

样例 2 解释

注意答案可能不适合 32 位整数。

数据范围

• $3\ \leq\ N\ \leq\ 10^5$
• $1\ \leq\ a_i\ \lt\ b_i\ \leq\ N$
• 给定的图是一棵树。