已知藏宝图上标有若干个排成一条直线的金矿,每个矿里有一定数量的金子,如下表所示。
每个矿中都有一张说明书,说明在挖完此矿的金子后还可继续挖哪些矿,如下图所示。
挖矿规则为可以从任何一个矿开始,到任何一个矿结束,同时挖完这个矿中的金子之后,可以选择它可继续挖的矿之一继续挖,但只能选择一条。如上图中,挖完1矿后,可挖2矿,再挖5矿,6矿,……但只可以向右挖,不能回头向左挖。 请问如何挖才能挖出最多的金子?
第一行为一个整数n,表示有n个矿。 第二行为n个整数,表示这n个矿的金子数。 随后n行,有多个数字表示每个矿的编号,其中第一个数字表示某个矿的编号,后面如果还有数字,表示某个矿挖完后还能再挖哪些矿。
最多挖出的金子数。
3 1 1 1 1 2 3 2 3 3
3
1\leq n\leq1 000
时间限制 | 1 秒 |
内存限制 | 128 MB |