산악 투어

당신은 에베레스트산 정상에 있으며, 그곳에 있는 멋진 등산로를 모두 즐기고 싶다. 하지만 과거의 경험을 통해 에베레스트산을 혼자 돌아다니는 것은 좋지 않다는 것을 알고 있다. 어둠 속에서 길을 잃을 수도 있기 때문이다! 그래서 미리 정해진 시간에 여행 안내원과 함께 하이킹을 하려고 한다.

산에는 C개의 캠프가 있으며(번호는 1부터 C까지이다), 단방향 하이킹 투어는 2 × C개이다(번호는 1부터 2 × C까지이다). 각 하이킹 투어는 한 캠프에서 출발하여 서로 다른 캠프에서 끝나며, 그 사이에 다른 캠프를 지나지 않는다. 에베레스트산에는 사람이 드물고 사업도 한산하다. 각 캠프에서 출발하는 하이킹 투어는 정확히 2개이고, 각 캠프에 도착하는 하이킹 투어도 정확히 2개이다.

각 하이킹 투어는 매일 운행한다. 투어 1과 2은 캠프 1에서 출발하고, 투어 3과 4은 캠프 2에서 출발하는 식이다. 일반적으로 투어 2 × i - 1과 투어 2 × i는 캠프 i에서 출발한다. i번째 하이킹 투어는 번호가 $E_{i}$인 캠프에서 끝나고, $L_{i}$시에 출발하며, 소요 시간은 정확히 $D_{i}$시간이다.

현재 시각은 0시이며, 하루의 각 시각에는 0부터 23까지의 번호가 붙어 있다. 당신은 번호가 1인 캠프에 있으며, 각 하이킹 투어를 정확히 한 번씩 이용하고 번호가 1인 캠프로 돌아오려고 한다. 하이킹 투어를 이용하지 않고 캠프 사이를 이동할 수는 없다. 캠프에 있는 동안에는 하이킹 투어를 이용하기 전에 원하는 만큼의 시간 동안(전혀 기다리지 않는 경우도 포함한다) 기다릴 수 있지만, 하이킹 투어가 출발하는 바로 그 순간에만 해당 투어를 시작할 수 있다.

투어 일정을 살펴본 결과, 목표를 달성하는 것이 분명히 가능하다는 사실을 알아냈지만, 가능한 한 빨리 달성하고 싶다. 경로를 최적으로 계획한다면 모든 투어를 마치는 데 몇 시간이 걸리는가?

제한

시간 제한: 테스트 세트당 20초. 메모리 제한: 1 GB. 1 ≤ T ≤ 100. 1 ≤ $E_{i}$ ≤ C. 모든 i에 대해 $E_{i}$ ≠ ceiling(i / 2). (어떤 하이킹 투어도 출발 캠프와 도착 캠프가 같지 않다.) 모든 j에 대해 {j의 크기 : $E_{j}$ = i} = 2. (각 캠프에서 정확히 두 개의 투어가 끝난다.) 0 ≤ $L_{i}$ ≤ 23. 1 ≤ $D_{i}$ ≤ 1000. 캠프 1에서 출발하여 그곳에서 끝나고 각 하이킹 투어를 정확히 한 번씩 포함하는 경로가 적어도 하나 존재한다.

작은 데이터 세트 (테스트 세트 1 - 공개)

2 ≤ C ≤ 15.

큰 데이터 세트 (테스트 세트 2 - 비공개)

2 ≤ C ≤ 1000.

입력의 첫 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 캠프의 수를 나타내는 정수 C가 있는 한 줄로 시작한다. 그다음에는 2 × C개의 줄이 더 주어진다. 이 줄들 중 i번째 줄은(1부터 세기 시작한다) 번호가 floor((i + 1) / 2)인 캠프에서 출발하는 하이킹 투어 하나를 나타내며, 위에서 설명한 세 정수 $E_{i}$, $L_{i}$, $D_{i}$을 포함한다. 이 형식에 따라 각 캠프에서 정확히 두 개의 투어가 출발함이 보장된다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호이며(1부터 시작한다), y는 위에서 설명한 목표를 달성하는 데 걸리는 최소 시간이다.

예제 케이스 #1에서 최적의 계획은 다음과 같다.

• 캠프 1에서 한 시간 동안, 1시가 될 때까지 기다린다.

• 1시에 캠프 1을 떠나 5시간짜리 하이킹 투어를 이용하고, 6시에 캠프 2에 도착한다.

• 즉시 6시에 캠프 2을 떠나 3시간짜리 하이킹 투어를 이용하고, 9시에 캠프 1에 도착한다.

• 캠프 1에서 15시간 동안, 다음 날 0시가 될 때까지 기다린다.

• 0시에 캠프 1을 떠나 3시간짜리 하이킹 투어를 이용하고, 3시에 캠프 2에 도착한다.

• 캠프 2에서 1시간 동안, 4시가 될 때까지 기다린다.

• 4시에 캠프 2을 떠나 4시간짜리 하이킹 투어를 이용하고, 8시에 캠프 1에 도착한다.

이렇게 하면 1일과 8시간, 즉 32시간 만에 목표를 달성한다. 다른 모든 계획은 시간이 더 오래 걸린다.

예제 케이스 #2에서는 모든 투어가 같은 시각에 출발하고 소요 시간도 같다. 어떤 투어든 마친 뒤 즉시 다른 투어를 이용할 수 있다. 테스트 케이스에 나타나는 순서대로 투어에 1부터 8까지 번호를 붙이면, 최적 계획 중 하나는 다음과 같다: 1, 5, 4, 7, 6, 2, 3, 8.