방송망

한 방송사가 유선 방송망을 설치하려고 한다. 방송망은 방송국을 루트로 하는 트리이다. 터미널 노드는 사용자이고, 터미널이 아닌 노드는 방송 신호를 전달하는 송신기이다. 루트는 방송국이면서 송신기이며, 루트도 터미널도 아닌 노드는 중간 송신기이다.

각 간선에는 방송 라인을 설치하는 비용이 있다. 총 방송 비용은 설치한 모든 라인의 비용 합이다.

사용자마다 방송을 시청할 때 지불하는 시청료가 미리 정해져 있다. 방송국에서 어떤 사용자까지 이어지는 모든 라인을 설치하면 그 사용자에게 방송을 제공하고 시청료를 받을 수 있다.

설치할 방송 라인을 적절히 골라 총 시청료에서 총 방송 비용을 뺀 값이 음수가 되지 않게 하면서, 방송을 제공할 수 있는 사용자 수의 최댓값을 구하라.

첫 줄에 N과 M이 주어진다. (2 ≤ N ≤ 3,000, 1 ≤ M ≤ N-1) N은 트리의 전체 노드 수, M은 터미널 노드 수이다. 루트는 1번이다. 루트가 아닌 송신기는 2번부터 N-M번까지이고, 사용자(터미널 노드)는 N-M+1번부터 N번까지이다.

다음 N-M개의 줄에는 각 송신기 1, 2, ..., N-M의 정보가 순서대로 주어진다.

K A1 C1 A2 C2 ... AK CK

K는 해당 송신기가 직접 연결하는 자식 노드 수이다. Ai는 자식 노드 번호이고, Ci는 그 노드로 가는 방송 라인의 설치 비용이다.

마지막 M개의 줄에는 N-M+1번 사용자부터 N번 사용자까지의 시청료가 순서대로 주어진다.

손해를 보지 않도록 방송을 제공할 수 있는 최대 사용자 수를 출력한다.