题目描述

某电视网络计划直播一场重要的足球比赛。其发射器与用户组成的网络可以表示为一棵树。树的根节点是发射比赛信号的发射器，叶子节点是潜在用户，其余节点为中继发射器。

信号从一个发射器传输到另一个发射器或用户的费用已知。整个广播的总费用是所有单独信号传输费用的总和。

每个用户愿意支付一定金额观看比赛，电视网络需决定是否为其提供信号。

请编写程序，计算在电视网络不亏损的情况下，能够观看比赛的最大用户数量。

输入

• 第一行包含两个整数 $N$ 和 $M$（$2 \leq N \leq 3000$，$1 \leq M \leq N-1$），分别表示树的节点数和潜在用户数。
  • 树的根节点编号为 $1$，其他发射器编号为 $2$ 至 $N-M$，潜在用户编号为 $N-M+1$ 至 $N$。
• 接下来的 $N-M$ 行描述发射器的传输信息，格式为：
  K A1 C1 A2 C2 ... AK CK
  表示该发射器可向 $K$ 个发射器或用户传输信号，每个目标由编号 $A$ 和传输费用 $C$ 描述。
• 最后一行包含 $M$ 个整数，表示每个用户愿意支付的金额。

输出

• 输出一行，表示在不亏损的情况下能够服务的最大用户数量。

输入样例 1

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

输出样例 1

5

来源

克罗地亚信息学奥林匹克 2002 决赛 - 第二天