A6286. 有线电视网

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

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

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

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

第一行包含两个用空格隔开的整数 $N$ 和 $M$：

- $N$ 为整个有线电视网的结点总数；
- $M$ 为用户终端的数量。

其中 $2 \le N \le 3000$，$1 \le M \le N - 1$。

结点按如下方式编号：

- 根结点（现场直播站）编号为 $1$；
- 其他转播站编号为 $2$ 到 $N - M$；
- 用户终端编号为 $N - M + 1$ 到 $N$。

接下来有 $N - M$ 行，第 $i+1$ 行表示第 $i$ 个转播站的数据，格式为：

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

含义为：

- 该转播站下接有 $K$ 个结点（可以是转播站或用户终端）；
- 对于每个这样的结点，给出一对整数 $(A_j, C_j)$：
- $A_j$ 为下挂结点的编号；
- $C_j$ 为从当前转播站传输信号到结点 $A_j$ 的费用。

最后一行包含 $M$ 个整数，依次表示各个用户终端愿意支付的费用。
第一个数对应结点 $N-M+1$，第二个数对应结点 $N-M+2$，以此类推。

单次传输成本和用户愿意交的费用均不超过 $10$。

输出仅一行，包含一个整数，表示在不亏本的前提下，最多可以让多少个用户观看比赛。

## 说明/提示

样例中共有 5 个结点：

- 结点 ① 为根结点（现场直播站）；
- 结点 ② 为中转站；
- 结点 ③、④、⑤ 为用户终端（共 $M=3$ 个），编号从 $N-M+1=3$ 到 $5$。

它们愿意支付的费用分别为 $3, 4, 2$。

从结点 ①：

- 可以传送信号到结点 ②，费用为 $2$；
- 可以传送信号到结点 ⑤，费用为 $3$。

从结点 ②：

- 可以传送信号到结点 ③，费用为 $2$；
- 可以传送信号到结点 ④，费用为 $3$。

如果让所有用户（③④⑤）都能收看，传输总费用为：

$2 + 3 + 2 + 3 = 10$，而用户愿意支付总费用为 $3 + 4 + 2 = 9$，有线电视网会亏本。

而如果只让用户 ③ 和 ④ 收看，传输费用为 $2 + 2 + 3 = 7$，用户支付总费用为 $3 + 4 = 7$，刚好不亏本，并且观看转播的用户数为 $2$，即为最优答案。

---

数据范围：

- $2 \le N \le 3000$
- $1 \le M \le N - 1$
- 传输费用和用户费用均为不超过 $10$ 的非负整数。