더블릿 방송회사에서는 야구를 중계하는 유료방송을 보내는데, 이에 소비자는 별도의 돈을 내서라도, 이 방송을 보겠다고 한다. 물론 돈을 내지 않으면, 방송도 보내지 않는다.

더블릿 방송회사는 소비자에게 유료방송을 공급하기 위해서 다음과 같은 공급계획을 세웠다.

공급계획

정점들은 중계자와 사용자로 구성되는데, 단말 정점은 사용자이고, 그 외는 중계자(1 번은 방송회사이면서 중계자임)이다. 사용자의 수가 M 이면, 중계자는 1~N-M 번이 된다.

1 번 정점은 방송회사이다. 방송회사는 1 번 정점에서 시작하여 중계자나 소비자에게 방송을 보낸다.

예를 들어 <그림 1>과 같이 트리 네트워크가 구성되었다면, 이 때, 3, 4, 5 번은 소비자이고, 1 번은 방송회사이고, 2 번은 중계자이다. 이 때, 간선은 방송을 전달하는데 드는 비용이고, 소비자 아래에 있는 괄호안의 숫자는 소비자가 부담할 수 있는 요금이다.

문제는 소비자가 요금을 부담한다고 하여도 방송을 전달하는데 드는 비용이 더 많다면, 방송을 전달할 수 없다. 그러나, 다른쪽에서 남는 이익금을 대체하여 손해나지 않으면서, 최대 몇 명의 소비자에게 방송을 할 수 있을지를 알아내는 것이 더블릿의 고민이다.

더블릿을 도와 방송을 볼 수 있는 소비자가 최대 몇 명인지를 출력하여라. 제한 시간은 2 초이다.

입력 형식

2~N-M+1 번째 줄 : 방송회사는 1 번이고 M 이 소비자의 수라면 중계회사는 N-M(1번 포함)이다. 둘째 줄부터 주어지는 데이터는 1번과 중계자가 다른 중계자 또는 소비자에게 방송을 전달할 때 드는 비용에 대해 주어진다.
둘째 줄은 1 번, 셋째 줄은 2 번, ...N-M+1번째 줄은 N-M 번 중계자에 대한 내용이다. 각 줄은 i 번째 중계자에 대해 다음과 같은 정보가 주어진다. K A1 C1 A2 C2 ...... Ak Ck K 는 i 번째 중계자가 몇 명의 다른 중계사나 소비자에게 방송을 전달할 수 있는지를 나타내는 수이다. Aj 는 중계사 또는 소비자의 번호이고, Cj 는 그때의 비용이다.

N-M+2 번째 줄 : 마지막 줄에는 N-M+1 번부터 N 번까지의 M 명의 소비자가 부담하는 요금이 주어진다.

출력 형식

입출력 예

입력 예 1

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

출력 예 1

2

입력 예 2

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

출력 예 2

3

입력 예 3

9 6
3 2 2 3 2 9 3
2 4 2 5 2
3 6 2 7 2 8 2
4 3 3 3 1 1

출력 예 3

5

출처:Croatia OI 2002 Final Exam - Second Day
원문:http://poj.org/problem?id=1155
추천:ainta