생존자 (Small)

당신은 무인도에 조난당했다. 다행히 음식이 든 상자를 하나 챙겼지만, 풀 한 포기 자라지 않는 돌섬인 데다 낚시할 방법도 없어서 음식을 더 구하지 못한다.

상자를 확인해 보니 음식은 모두 $N$ 개다. 각 음식 $i$ 마다 지금 기준으로 남은 유통기한 $P_i$ 와 그 음식을 먹었을 때 허기를 참을 수 있는 시간 $S_i$ 를 알아냈다.

음식을 먹는 규칙은 다음과 같다.

지금, 즉 0분에 첫 음식을 먹는다.
$P_i$ 와 $S_i$ 의 단위는 모두 분이다.
유통기한이 지난 음식은 곧바로 폐기한다. 즉 음식 $i$ 는 $P_i$ 분 이하인 시각에만 먹는다. 남은 유통기한이 0인 음식은 지금 당장 먹지 않으면 폐기한다.
허기를 참는 동안에는 아무것도 먹지 않는다. 음식 $i$ 를 $t$ 분에 먹었다면 다음 음식은 정확히 $t + S_i$ 분에 먹는다.
허기가 시작되는 순간에 먹을 음식이 남아 있지 않으면 그 자리에서 굶어 죽는다.

먹을 음식과 먹는 순서를 마음대로 정할 때, 무인도에서 살아남는 최대 시간을 구하라. 마지막으로 먹은 음식이 $t$ 분에 들어갔고 그 음식의 값이 $S$ 라면 생존 시간은 $t + S$ 분이다.

첫 줄에 테스트 케이스의 개수 $T$ 가 주어진다. 이어서 각 테스트 케이스가 다음 형식으로 주어진다.

N
P1 S1
P2 S2
...
PN SN

각 테스트 케이스 $x$ 마다 Case #x: y 형식으로 한 줄씩 출력한다. $y$ 는 그 테스트 케이스에서 무인도에서 살아남는 최대 시간이다.