Broadcast Network

A broadcasting company wants to build a wired broadcast network. The network is a tree rooted at the broadcasting company. Terminal nodes are users, and every non-terminal node is a transmitter. The root is both the broadcasting company and a transmitter; non-root, non-terminal nodes are intermediate transmitters.

Each edge has a cost to install the broadcast line on that edge. The total broadcast cost is the sum of the costs of all installed lines.

Each user has a predetermined fee they will pay when they can watch the broadcast. If every line on the path from the root to a user is installed, the company can serve that user and receive that fee.

Choose which broadcast lines to install so that total fees minus total broadcast cost is not negative. Find the maximum number of users that can be served.

The first line contains N and M. (2 ≤ N ≤ 3,000, 1 ≤ M ≤ N-1) N is the total number of nodes in the tree, and M is the number of terminal nodes. The root is node 1. Non-root transmitters are numbered from 2 through N-M, and users (terminal nodes) are numbered from N-M+1 through N.

The next N-M lines give the information for transmitters 1, 2, ..., N-M, in order.

K A1 C1 A2 C2 ... AK CK

K is the number of child nodes directly connected from that transmitter. Ai is a child node number, and Ci is the cost of installing the broadcast line to that child.

The final M lines contain the user fees for users N-M+1 through N, in order.

Print the maximum number of users that can be served without taking a loss.