시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 0 0 0 0.000%

문제

월드 방송국에서 유선으로 방송을 하고자 한다. 방송망의 형태는 방송국이 루트인 트리의 형태가 될 것이다. 트리의 터미널 노드들은 사용자를 의미하며 트리에서 터미널을 제외한 노드는 송신기 역할을 하게 된다. (루트는 방송국이면서 송신기이며, 루트와 터미널이 아닌 노드들은 중간 송신기라고 불려진다)

한 노드에서 다른 노드로 방송 라인을 설치할 때 드는 비용이 주어진다. 총 방송 비용이란 설치한 방송 라인의 비용을 모두 더한 값이다.

같은 방송망에 있지만 각각의 사용자가 내는 돈은 다를 수 있으며 각각 사용자가 방송을 보게 될 때 지불할 돈이 미리 주어진다.

방송국에서는 방송 라인을 하나 설치할 때 지출을 하게 된다. 또한 방송망이 방송국에서 사용자까지 도달되면 방송국은 그 사용자에게서 시청료를 받게 된다.

방송라인을 적절히 설치해서 방송국이 손해를 보지 않으면서 방송을 해줄 수 있는 최대 사용자는 몇 명인가? (손해를 보지 않는다는 말은 총 시청료 - 총 방송 비용 ≥ 0 임을 의미한다)

입력

첫 줄에 N M이 입력된다. (2 ≤ N ≤ 3,000, 1 ≤ M ≤ N-1)
N은 트리의 노드 개수이고 M은 트리의 터미널 노드 개수이다.
노드의 번호는 트리의 루트가 1이며, 루트가 아닌 다른 송신기들은 2부터 N-M까지, 사용자들(터미널노드들)의 번호는 N-M+1부터 N까지 이다.
두 번째 줄부터 N-M개의 줄에 다음과 같은 형식으로 송신기 정보가 주어진다.
K A1 C1 A2 C2 ... Ak Ck
K는 그 송신기가 송신하는 노드의 개수이며 A는 그 노드의 이름 C는 그 비용을 의미한다.
그 이후의 M개의 라인에는 M명의 사용자의 시청료가 각각 입력된다.

출력

최대 사용자 수를 출력한다.

예제 입력

5 3
2 2 2 5 3
2 3 2 4 3
3 4 2

예제 출력

2

힌트