시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 512 MB 60 26 18 51.429%

문제

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

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

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

 

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

 

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

입력

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


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

제약조건

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

출력

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

예제 입력

2
3
3 4
0 4
4 4
3
3 9
0 4
4 4

예제 출력

Case #1: 8
Case #2: 9

힌트