{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"A 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).\r\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.\r\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.\r\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."}},{"title":"Input","value":{"format":"HTML","content":"The 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.\r\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.\r\u003cbr\u003eThe following N-M lines contain data about the transmitters in the following form:\r\u003cbr\u003eK A1 C1 A2 C2 ... AK CK\r\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.\r\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."}},{"title":"Output","value":{"format":"HTML","content":"The first and the only line of the output file should contain the maximal number of users described in the above text."}},{"title":"Sample","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\n"}}]}