题目描述

小W非常喜欢挖金矿，因为这会使他money+=inf;

这天，他获得了一张藏宝图。

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

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

挖矿规则为可以从任何一个矿开始，到任何一个矿结束，同时挖完这个矿中的金子之后，可以选择它可继续挖的矿之一继续挖，但只能选择一条。如上图中，挖完 $1$ 矿后，可挖 $2$ 矿，再挖 $5$ 矿，$6$ 矿，……

但只可以向右挖，不能回头向左挖。

小W想要尽可能多的金子，于是他问你：如何挖才能挖出最多的金子？

输入格式

输入共 $n+2$ 行。

第一行为一个整数 $n$，表示有 $n$ 个矿。

第二行为 $n$ 个整数，表示这 $n$ 个矿的金子数，其中第 $i$ 个数的金子数为 $a_i$。

接下来 $n$ 行，第 $i$ 行描述编号为 $i$ 的矿（因此这 $n$ 行的首个数字依次为 $1, 2, \ldots, n$）。每行第一个数字是该矿的编号，后面跟着若干个数字，表示挖完该矿之后还可以继续挖的矿的编号。

注意：由于只能向右挖，每行后面列出的编号中，只有大于该矿编号的才是合法后继；小于该矿编号的编号是干扰项，请忽略它们。

输出格式

最多挖出的金子数。

输入输出样例 #1

输入 #1

3
1 1 1
1 2 3
2 3
3

输出 #1

3

说明

数据范围

• 对于 $20\%$ 的数据，$1 \le n \le 20$。
• 对于 $50\%$ 的数据，$1 \le n \le 100$。
• 对于 $100\%$ 的数据，$1 \le n \le 1000$，$1 \le a_i \le 10^9$。