문제
조이는 에베레스트를 등산하기로 했다.
에베레스트에는 C개의 캠프가 있고, 한 캠프에서 다른 캠프로 이동하는 2C개의 단방향 투어가 있다.
각 캠프에는 사람이 별로 없기 때문에, 모든 캠프는 정확히 2개의 출발하는 투어과 2개의 도착하는 투어가 있다.
에베레스트는 어두울 때 이동하면 매우 위험하기 때문에 시간을 맞춰 이동하는 것이 매우 중요하다.
하루는 24시간이며, 0부터 23까지의 숫자로 나타난다.
각 투어는 출발해야 하는 시간이 정확히 정해져 있다.
구체적으로, i번째 캠프를 떠나는 투어는 2i-1번째와 2i번째 투어이다.
i번째 투어는 E_i번 캠프에 도착하며, L_i시에 떠나야 하고, D_i 시간이 걸린다.
조이는 0시에 1번 캠프에 도착했다. 조이는 2C개의 모든 투어를 정확히 1번만 체험하고 1번 캠프로 돌아오는 것이 목표이다.
조이는 한 캠프에 도착한 뒤, 캠프에서 다음 투어를 체험하기 위해 0시간 이상 대기할 수 있으며, 도착하자마자 바로 떠날 수도 있다.
단, 투어를 제외한 다른 방법으로 이동할 수는 없다.
조이를 도와 2C개의 모든 투어를 체험하기 위한 최소 시간을 구해주자.
입력
첫 번째 줄에 캠프의 개수 C가 주어진다. (2≦C≦1000)
두 번째 줄부터 2C개의 줄에 각 투어에 대한 정보가 순서대로 주어진다.
i번째 줄에는 E_i, L_i, D_i가 순서대로 주어지며,
이는 i번째 투어가 [(i+1)/2]에서 출발하여 E_i에 도착하고, L_i시간에 출발하며, D_i시간이 걸리다는 것을 의미한다.
모든 i에 대해, E_i ≠ ceiling(i / 2) (자기 자신으로 돌아오는 투어는 없다.) 모든 i에 대해, E_j = i인 j는 2개이다.
(모든 캠프에 대해 그 캠프가 도착점인 투어는 2개이다) 0 ≤ L_i ≤ 23 1 ≤ D_i ≤ 1000
[제한]
부분 문제 1 [20점] 2≦C≦15
부분 문제 2 [80점] 2≦C≦1000
출력
예제 #1
2
2 1 5
2 0 3
1 4 4
1 6 3
32
예제 #2
4
3 0 24
2 0 24
4 0 24
4 0 24
2 0 24
1 0 24
3 0 24
1 0 24
192
로그인해야 코드를 작성할 수 있어요.