{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003eA TV-network plans to broadcast an important football match. Their network of transmitters and users can be represented as a tree. The root of the tree is a transmitter that emits the football match, the leaves of the tree are the potential users and other vertices in the tree are relays (transmitters).\n\u003cbr\u003eThe price of transmission of a signal from one transmitter to another or to the user is given. A price of the entire broadcast is the sum of prices of all individual signal transmissions.\n\u003cbr\u003eEvery user is ready to pay a certain amount of money to watch the match and the TV-network then decides whether or not to provide the user with the signal.\n\u003cbr\u003eWrite a program that will find the maximal number of users able to watch the match so that the TV-network\u0027s doesn\u0027t lose money from broadcasting the match.\u003c/div\u003e\n一个广播电视台打算广播球赛,这个广播的连接关系是一个树关系,根节点是一电视台,叶子节点是客户,其余节点是中转站,电视台也算是中转站,每一个中转站都连接着一些其他中转站或者叶子,连接的路线有一个权值,代表通过这条道路的花费。而每一个叶子节点,也就是客户,有会对于转播的节目有一定数额的付款。问电视台在不亏损的情况下,最多能够让多少个客户看到球赛。"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003eThe first line of the input file contains two integers N and M, 2 \u0026lt;\u003d N \u0026lt;\u003d 3000, 1 \u0026lt;\u003d M \u0026lt;\u003d N-1, the number of vertices in the tree and the number of potential users.\n\u003cbr\u003eThe root of the tree is marked with the number 1, while other transmitters are numbered 2 to N-M and potential users are numbered N-M+1 to N.\n\u003cbr\u003eThe following N-M lines contain data about the transmitters in the following form:\n\u003cbr\u003eK A1 C1 A2 C2 ... AK CK\n\u003cbr\u003eMeans that a transmitter transmits the signal to K transmitters or users, every one of them described by the pair of numbers A and C, the transmitter or user\u0027s number and the cost of transmitting the signal to them.\n\u003cbr\u003eThe last line contains the data about users, containing M integers representing respectively the price every one of them is willing to pay to watch the match.\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"ptx\" lang\u003d\"en-US\"\u003eThe first and the only line of the output file should contain the maximal number of users described in the above text.\u003c/div\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e9 6\n3 2 2 3 2 9 3\n2 4 2 5 2\n3 6 2 7 2 8 2\n4 3 3 3 1 1\u003c/pre\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cpre class\u003d\"sio\"\u003e5\u003c/pre\u003e"}}]}