프로젝트 스케줄링

퍼트(PERT)는 큰 프로젝트를 여러 작업으로 나누고, 각 작업에 필요한 기간을 정하고, 어떤 작업이 끝나야 다른 작업을 시작할 수 있는지를 정리하는 프로젝트 관리 기법이다. 이렇게 정리한 내용은 차트로 그린다.

위 그림은 첫 번째 예제 입력에 해당하는 차트다. 작업 A, B, C, D, E, F는 각각 5일, 3일, 2일, 2일, 4일, 2일이 걸린다. 작업 E는 C와 D가 모두 끝나야 시작하고, A가 끝나면 B와 D는 동시에 진행할 수 있다. 서로를 기다리지 않는 작업은 몇 개든 동시에 진행한다.

차트가 주어지면 프로젝트를 끝내는 데 걸리는 최소 시간을 구하는 프로그램을 작성하시오.

입력은 1줄에서 26줄까지 주어지고, 한 줄이 작업 하나를 나타낸다. 같은 작업 이름이 두 번 나오지는 않는다. 각 줄은 다음 순서로 이루어진다.

1. 작업 이름을 나타내는 영문 대문자 하나
2. 작업을 끝내는 데 필요한 날짜 수를 나타내는 1,000 이하의 자연수
3. 이 작업을 시작하기 전에 끝내야 하는 작업의 이름을 띄어쓰기 없이 붙여 쓴 영문 대문자 0개에서 25개

세 번째 항목이 없으면 그 줄은 두 항목으로 끝난다. 세 번째 항목에 적힌 작업은 모두 입력에 주어지며, 항상 모든 작업을 완료할 수 있는 입력만 주어진다.

첫째 줄에 모든 작업을 끝내는 데 걸리는 시간의 최솟값을 출력한다.