题目描述

某通信公司计划为一场大型体育赛事提供实时信号转播服务。他们的转播网络与用户终端构成一棵树状结构：根节点位于赛事现场，叶子节点为各用户终端，其余节点为信号中转站。

从一个转播站到另一个转播站、以及从转播站到用户终端的信号传输费用都是已知的，一场转播的总费用等于所有被选中传输路径的费用之和。

每位用户愿意支付一笔费用观看比赛，通信公司有权决定为哪些用户传输信号。请找出一个方案，使得公司在不亏损的前提下，服务尽可能多的用户。

输入格式

输入第一行包含两个整数 $N$ 和 $M$，其中 $2\le N\le 3000$，$1\le M\le N-1$。$N$ 为网络中结点总数，$M$ 为用户终端数量。

根结点编号为 $1$，其余中转站编号为 $2$ 到 $N-M$，用户终端编号为 $N-M+1$ 到 $N$。

接下来的 $N-M$ 行描述各中转站的下接信息。第 $i+1$ 行表示第 $i$ 个中转站的数据，格式为：

$K\ \ A_1\ \ C_1\ \ A_2\ \ C_2\ \ \ldots\ \ A_K\ \ C_K$

其中 $K$ 表示该中转站下接 $K$ 个结点，每对整数 $A$ 和 $C$ 分别表示子结点编号和传输费用。

最后一行依次列出所有用户愿意支付的金额。单次传输费用和用户愿意支付的金额均不超过 $10$。

输出格式

一行一个整数，表示公司最多能服务的用户数量。

样例

5 3
2 2 2 5 3
2 3 2 4 3
3 4 2

2

5 3
2 2 2 5 3
2 3 2 4 3
4 4 2

3

9 6
3 2 2 3 2 9 3
2 4 2 5 2
3 6 2 7 2 8 2
4 3 3 3 1 1

5

提示

样例解释

如图所示，共有五个结点。结点 ① 为根结点（赛事现场），② 为中转站，③④⑤ 为用户端，他们愿意支付的金额分别为 $3$、$4$、$2$。

从 ① 到 ② 费用 $2$，从 ① 到 ⑤ 费用 $3$，从 ② 到 ③ 费用 $2$，从 ② 到 ④ 费用 $3$。

若服务全部用户，总费用 $2+3+2+3=10$，大于用户总支付 $3+4+2=9$，公司亏损。只服务 ③④ 则不亏损。

限制与约定

$2\le N\le 3000$，$1\le M\le N-1$，传输费用和用户支付金额均不超过 $10$。