건물 완성 시간

한 회사가 새로운 전략 시뮬레이션 게임을 개발하고 있다. 핵심 기능은 이미 완성되었고, 종족별 균형과 전체 플레이 시간 같은 요소를 조정하는 일만 남았다.

실제 플레이 시간은 상황에 따라 달라질 수 있으므로, 모든 건물을 짓는 데 필요한 최소 시간으로 이를 근사하려고 한다. 다만 어떤 건물은 다른 건물이 먼저 완성되어야 지을 수 있으므로 계산이 단순하지만은 않다. 예를 들어 방어용 건물을 짓기 전에 생산용 건물을 먼저 지어야 하는 경우가 있을 수 있다. 여러 건물은 동시에 지을 수 있다.

자원은 무한히 있고, 건설 명령을 내리는 데는 시간이 걸리지 않는다고 가정한다.

첫째 줄에 건물의 종류 수 N (1 <= N <= 500)이 주어진다.

다음 N개의 줄에는 각 건물의 정보가 한 줄에 하나씩 주어진다. 각 줄은 그 건물을 짓는 데 걸리는 시간으로 시작하고, 이어서 그 건물을 짓기 전에 먼저 완성되어야 하는 건물들의 번호가 주어진다. 건물 번호는 1부터 N까지이며, 각 줄은 -1로 끝난다.

각 건설 시간은 100000 이하의 자연수이다. 모든 건물을 완성할 수 있는 입력만 주어진다.

N개의 줄을 출력한다. i번째 줄에는 i번 건물이 완성되기까지 걸리는 최소 시간을 출력한다.