{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"一个电视网络计划播出一场重要的足球比赛。他们的发射器和用户网络可以表示为一棵树。树的根是发射器,发射足球比赛信号,叶子是潜在用户,树中的其他顶点是中继器(发射器)。\n\u003cbr\u003e从一个发射器到另一个发射器或用户的信号传输价格已知。整个广播的价格是所有单个信号传输价格的总和。\n\u003cbr\u003e每个用户愿意支付一定金额来观看比赛,电视网络然后决定是否向用户提供信号。\n\u003cbr\u003e编写一个程序,找到最大数量的用户能够观看比赛,以便电视网络不会因广播比赛而亏损。"}},{"title":"输入","value":{"format":"HTML","content":"输入文件的第一行包含两个整数N和M,2 \u003c\u003d N \u003c\u003d 3000,1 \u003c\u003d M \u003c\u003d N-1,树中顶点的数量和潜在用户的数量。\n\u003cbr\u003e树的根用数字1标记,其他发射器从2到N-M编号,潜在用户从N-M+1到N编号。\n\u003cbr\u003e接下来的N-M行包含关于发射器的数据,格式如下:\n\u003cbr\u003eK A1 C1 A2 C2 ... AK CK\n\u003cbr\u003e表示一个发射器将信号传输给K个发射器或用户,每个发射器或用户由数字A和C描述,即发射器或用户的编号和传输信号的成本。\n\u003cbr\u003e最后一行包含关于用户的数据,包含M个整数,分别表示他们愿意支付观看比赛的价格。"}},{"title":"输出","value":{"format":"HTML","content":"输出文件的第一行应包含上述文本中描述的最大用户数量。"}},{"title":"样例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e9 6\r\n3 2 2 3 2 9 3\r\n2 4 2 5 2\r\n3 6 2 7 2 8 2\r\n4 3 3 3 1 1\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e5\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}