时间限制：1秒　　内存限制：256M

---

【题目描述】

　　央视总台计划向偏远山区转播2026春晚节目。转播网络的结点和山区终端用户构成一棵树状结构，这棵树的根结点位于春晚现场，树叶为各个用户终端，其他中转点为该树的内部转播结点。

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

　　每个用户都准备了一笔观看春晚的费用，因为资源有限，不能保证所有用户最终能收看到节目，但中央电视台还是决定在不亏本的情况下使观看转播的用户尽可能多。

【输入格式】

　　第一行包含两个用空格隔开的整数 \(N\) 和 \(M\)，其中 \(1≤M≤N-1\)，\(N\) 为整个有线电视网的结点总数，\(M\) 为用户终端的数量。春晚现场为根，其编号为 1，其他的转播点编号为 2 到 \(N-M\)，山区终端用户编号为 \(N-M+1\) 到 \(N\)。
　　接下来的 \(N-M\) 行每行表示—个转播点的数据，第 \(i+1\) 行表示第 \(i\) 个转播点的数据，其格式如下：\(k s1 c1 s2 c2 … sk ck\)，\(k\) 表示该转播点下接 \(k\) 个结点（转播点或用户），每个结点对应一对整数 \(s\) 与 \(c\) ，\(s\) 表示结点编号，\(c\) 表示从当前转播点传输信号到结点 \(a\) 的费用。
　　最后一行依次表示所有用户为观看比赛而准备支付的钱数。

【输出格式】

　　仅一行，包含一个整数，表示上述问题所要求的最大用户数。

【输入输出样例1】

　Input

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

　Output

2

【样例1解释】

　　如图，共有五个结点。结点①为根结点，即现场直播点，②为一个中转点，③④⑤ 为用户端，共 M 个，编号从N-M+1到N，他们为观看比赛分别准备的钱数为 3、4、2。
　　从结点 ① 可以传送信号到结点 ②，费用为 2；
　　也可以传送信号到结点 ⑤，费用为 3（第二行数据所示）；
　　从结点 ② 可以传输信号到结点 ③，费用为2；
　　也可传输信号到结点 ④，费用为 3（第三行数据所示）。
　　如果要让所有用户（③④⑤）都能看上比赛，则信号传输的总费用为：2+3+2+3=10，大于用户愿意支付的总费用 3+4+2=9，有线电视网就亏本了，而只让 ③④ 两个用户看比赛就不亏本了。

【输入输出样例2】

　Input

13 7
3 2 5 3 2 13 3
2 4 3 10 1
1 5 1
3 7 2 8 3 9 2
2 6 3 12 2
1 11 1
3 4 2 5 7 3 2 

　Output

3

【数据限制】

　　- 对于 \(100\%\) 的数据，\(2≤N≤3000\)，单次传输成本和用户愿意交的费用均不超过10。

【来源】

　　Mr.he