12429번 - 생존자 (Small)

당신은 무인도에 조난당했다. 다행히 음식이 들어있는 상자를 하나 챙길 수 있었지만, 풀 한 포기 보이지 않는 돌 섬인데다 낚시를 할 방법이 없어서 추가적인 음식 공급은 어려운 상황이다.

잠깐의 확인을 통해, 음식이 전체 N개이고, 각 음식 i에 대해 남아 있는 유통기한 P_i와 먹으면 얼마 동안 허기를 참을 수 있는지를 나타내는 S_i에 대한 조사가 끝난 상황이다.

한편, 음식을 먹는 데는 다음과 같은 제약사항이 있다.

• 지금부터 음식을 먹기 시작한다.
• 남아있는 유통기한 P_i와 허기를 참을 수 있는 기간을 나타내는 S_i의 단위는 '분'으로 같다.
• 유통기한이 지난 음식은 바로 폐기한다. 즉, 남아있는 유통기한이 0인 음식은 지금 바로 먹지 않으면 폐기해야 하는 음식이다.
• 허기를 참을 수 있는 기간에는 다른 아무것도 먹지 않는다.
• 허기가 오기 시작하자마자 무언가 먹지 않으면 바로 굶어 죽는다.

이런 조건이 있을 때, 무인도에서 얼마만큼 생존할 수 있는지 구해보자.

입력의 첫 줄에는 테스트 케이스의 개수 T가 주어지고, 다음 줄부터는 다음과 같은 형식으로 각 테스트 케이스를 설명하는 입력이 주어진다.

N
P1 S1
P2 S2
P3 S3
...
PN SN

제약조건

• 모든 입력은 정수로 주어진다.
• 1 ≤ T ≤ 100.
• 1 ≤ N ≤ 10.
• 0 ≤ P_i ≤ 100.
• 1 ≤ S_i ≤ 100.

각 케이스 x에 대해, 무인도에서 생존할 수 있는 최대 시간 y를 "Case #x: y" 와 같은 꼴로 출력하시오.