描述

现有N个任务需要安排,第i个任务需要Li天时间完成。

任务可以在不连续的若干天内完成,但只能安排在可执行该任务的日期中。

此外,一个任务可能要在另一个任务完成后才能开始,不过,被依赖的任务不会再依赖另一个

每天至多只能安排一个任务,求:至少要多少天才能将所有任务安排完

输入格式

第一行是一个正整数N

接下来的2-N+1行,每行的第一个正整数是L1-LN,意义如上,第二个自然数D1-DN若为0,则代表其不依赖其他任务,否则代表该任务必须在对应编号任务完成后才能开始,最后若干个(≥Li个)互不相同的正整数,是第1-N个任务的可安排日,上述数字均用空格隔开

输出格式

一行一个自然数,为最少天数

样例输入

3
1 0 1 9 10
2 1 1 3 7 8
2 0 2 3 5

样例输出

7

数据范围与约定

40%的数据中,任务间没有依赖关系,N≤10;

100%的数据中,被依赖的任务数≤1,N≤30,日期不超过300,数据保证任务能在所给日期内安排完

样例解释

一种可能的方案:第1天安排任务1,第2、5天安排任务3,第3、7天安排任务2(其依赖任务1此时已完成)