만드는 중입니다

아직 만드는 중이라 바뀔 수 있습니다

생존자 (Small)

면접 대비

시간 제한5초메모리 제한512 MB

요약
각 음식의 유통기한을 지키면서 먹을 음식과 순서를 정해 생존 시간을 최대화합니다.
난이도

보통10점 중 5점

유형
백트래킹, 동적 계획법
정답자
아직 제출이 없습니다

문제

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

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

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

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

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

입력

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

N
P1 S1
P2 S2
...
PN SN

제약조건

  • 모든 입력은 정수다.
  • 1≤T≤1001 \le T \le 100
  • 1≤N≤101 \le N \le 10
  • 0≤Pi≤1000 \le P_i \le 100
  • 1≤Si≤1001 \le S_i \le 100

출력

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

예제5

  1. 예제 1

    입력
    2
3
3 4
0 4
4 4
3
3 9
0 4
4 4
    예상 출력
    Case #1: 8
Case #2: 9

  2. 예제 2

    입력
    1
1
0 1
    예상 출력
    Case #1: 1

  3. 예제 3

    입력
    3
1
100 100
1
0 100
1
50 7
    예상 출력
    Case #1: 100
Case #2: 100
Case #3: 7

  4. 예제 4

    입력
    2
4
0 3
0 9
0 1
0 5
3
0 100
0 100
0 100
    예상 출력
    Case #1: 9
Case #2: 100

  5. 예제 5

    입력
    2
2
10 1
5 100
2
5 100
10 1
    예상 출력
    Case #1: 101
Case #2: 101