题目描述

为了找到回家的路,张琪曼施展魔法,从高维空间召唤出了一种叫作"读者"的生物，据 说"读者"这种生物无所不能,他们可以穿越时空的限制，聆听到历史的声音、巨人的呐喊。 但这次"读者"却很严肃地警告她们,从远古起就阴魂不散的天顶星人已冲破封印再次降临 到了这个空间,她们若不早做准备,不仅她们所在的这个世界将变成修罗场,连"读者"所在 的时空也会受到牵连。最后"读者"交给她们一张藏宝图希望她们能收集足够多的魔法石能 量以对抗天顶星人的进攻。已知藏宝图上标有若干个排成一条直线的魔法石矿,每个矿里 有一定数量的魔法石,如表所示。

同时每个矿中都有一张说明书,说明在挖完此矿的魔法石后还可继续挖哪些矿，如 图所示。

挖矿规则为可以从任何一个矿开始,到任何一个矿结束,同时挖完这个矿中的魔法石之 后，可以选择它可继续挖的矿之一继续挖,但只能选择一条。如挖完$\red{1}$矿后,可挖$\red{2}$矿，再挖 $\red{5}$矿,$\red{6}$矿,...但只可以向右挖,不能回头向左挖。请问如何挖才能挖出最多的魔法石?

输入格式

第一行为一个整数$\red{n,}$表示有$\red{n(n≤}$$\red{1000)}$个矿。第二行为$\red{n}$个整数,表示这$\red{n}$个矿的魔 法石数。随后$\red{n}$行表示每个矿挖完后还能再挖哪些矿。

输出格式

最多挖出的魔法石数。

样例

输入样例

3
1 1 1
1 2 3
2 3
3

输出样例

3