301007 - 金矿

已知藏宝图上标有若干个排成一条直线的金矿，每个矿里有一定数量的金子，如下表所示。

每个矿中都有一张说明书，说明在挖完此矿的金子后还可继续挖哪些矿，如下图所示。

挖矿规则为可以从任何一个矿开始，到任何一个矿结束，同时挖完这个矿中的金子之后，可以选择它可继续挖的矿之一继续挖，但只能选择一条。如上图中，挖完1矿后，可挖2矿，再挖5矿，6矿，……但只可以向右挖，不能回头向左挖。 请问如何挖才能挖出最多的金子？

Input

第一行为一个整数n，表示有n个矿。 第二行为n个整数，表示这n个矿的金子数。 随后n行，有多个数字表示每个矿的编号，其中第一个数字表示某个矿的编号，后面如果还有数字，表示某个矿挖完后还能再挖哪些矿。

Output

最多挖出的金子数。

Examples

Input

3
1 1 1 
1 2 3
2 3
3

Output

3

Hint

1\leq n\leq1 000

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题