题目描述

某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构，这棵树的根结点位于足球比赛的现场，树叶为各个用户终端，其他中转站为该树的内部节点。

从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的，一场转播的总费用等于传输信号的费用总和。

现在每个用户都准备了一笔费用想观看这场精彩的足球比赛，有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。

写一个程序找出一个方案，使得有线电视网在不亏本的情况下让观看转播的用户尽可能多。

输入格式

输入文件的第一行包含两个用空格隔开的整数 $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 A1 C1 A2 C2 ... AK CK

$K$ 表示该转播站下接 $K$ 个结点（转播站或用户）。每个结点对应一对整数 $A$ 与 $C$，$A$ 表示结点编号，$C$ 表示从当前转播站传输信号到结点 $A$ 的费用。

最后一行依次表示所有用户为观看比赛而准备支付的钱数。单次传输成本和用户愿意支付的费用均不超过 $10$。

输出格式

输出文件仅一行，包含一个整数，表示在有线电视网不亏本的情况下，最多能让多少个用户观看转播。

说明/提示

对于样例一，结点 $1$ 是根结点，结点 $2$ 是中转站，结点 $3,4,5$ 是用户端，他们分别准备支付 $3,4,2$。

如果让所有三个用户观看，信号传输的总费用为 $2+3+2+3=10$，大于用户支付的总费用 $3+4+2=9$，有线电视网会亏本；只让用户 $3,4$ 观看则不会亏本，因此答案为 $2$。

数据范围与约定

输入文件的第一行包含两个用空格隔开的整数 $N$ 和 $M$，其中 $2\le N\le 3000$，$1\le M\le N-1$。$N$ 为整个有线电视网的结点总数，$M$ 为用户终端的数量。

最后一行依次表示所有用户为观看比赛而准备支付的钱数。单次传输成本和用户愿意支付的费用均不超过 $10$。

可见测试数据

输入数据 1

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

输出数据 1

2

输入数据 2

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

输出数据 2

3

输入数据 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

输出数据 3

5