Description

约翰有一份必须完成的$N（3≤N ≤10000）$个家务的清单。每个家务都需要一个整数时间$T （1≤T ≤100）$才能完成，并且可能还有其他家务必须在这个家务开始之前完成。至少有一个家务没有先决条件：第1号。家务$K （K >1）$只能以家务$1～K -1$作为先决条件。计算完成所有$N$ 个家务所需的最少时间。当然，可以同时进行彼此不依赖的家务。

Format

Input

第1行包含一个整数$N$ 。第$2～N +1$行描述每个家务，第2行包含家务1；第3行包含家务2，以此类推。每行都包含完成家务的时间、先决条件的数量$Pi （0≤Pi ≤100）$和$Pi$个先决条件。

Output

单行输出完成所有家务所需的最少时间。

Samples

7
5 0
1 1 1
3 1 2
6 1 1
1 2 2 4
8 2 2 4
4 3 3 5 6

23

来源

POJ1949