게임 개발

N개의 건물에 건설 시간과 선행 건물이 있다. 선행 건물이 모두 완성되어야 해당 건물을 짓기 시작할 수 있다. 각 건물을 완성하는 최소 시간을 구한다.

입력 형식에서 선행 건물 목록의 끝은 -1로 표시한다. 여러 선행 건물은 동시에 짓는다.

입력

첫째 줄에 건물 수 N이 주어진다.

다음 N개 줄에 건물 i의 건설 시간, 선행 건물 번호들이 주어지며, 마지막에 -1이 있다.

• 1 ≤ N ≤ 500
• 1 ≤ 건설 시간 ≤ 100,000

출력

각 건물이 완성되는 최소 시간을 순서대로 한 줄에 하나씩 출력한다.

예제 입력 1

5
10 -1
10 1 1 -1
4 1 1 -1
4 1 2 -1
3 2 3 4 -1

예제 출력 1

10
20
14
24
27