고향 음식 배달 (라지)

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

요약
예산과 건당 배달료, 가격과 보관 기간이 다른 음식이 있을 때 첫 배달일부터 매일 한 끼씩 먹을 수 있는 최대 일수를 구합니다.
난이도

보통10점 중 7점

유형
이분 탐색, 그리디, 정렬
정답자
아직 제출이 없습니다

문제

고향을 떠나 대도시로 이사했다. 새 동네는 다 마음에 드는데 음식만은 아니다. 고향 식당이 내놓는 음식(이하 고향 음식)은 이 지역에서 가장 맛있고, 그 맛이 계속 생각난다.

다행히 고향에서 가장 큰 식당이 배달을 한다. 한 번의 배달로 원하는 만큼 살 수 있고, 얼마를 사든 배달 한 번마다 배달비 FF가 똑같이 붙는다.

이 식당은 NN가지 음식을 판다. 음식 ii의 한 끼 가격은 PiP_i이고 신선도는 SiS_i이다. 한 끼는 하루치 식사이며, 한 번 먹은 끼니는 다시 먹지 못한다. 신선도는 배달받은 날부터 세어 그 음식을 먹을 수 있는 마지막 날까지의 일수다. 배달일이 dd일이면 음식 ii는 dd일부터 d+Sid + S_i일까지 먹을 수 있고, Si=0S_i = 0이면 배달 당일에 먹어야 한다.

한 번의 배달에서 돈이 되는 만큼 여러 종류를, 종류마다 여러 끼를 살 수 있다. 다만 신선도가 SiS_i인 음식을 한 배달에서 Si+1S_i + 1끼보다 많이 사면 먹기 전에 상하는 끼니가 반드시 생긴다.

이 식당의 배달은 아주 빨라서 주문한 당일에 모두 도착하고, 도착한 날 바로 먹어도 된다. 고향 음식을 구하는 방법은 배달뿐이다.

끼니 값과 배달비로 쓸 수 있는 돈 MM이 주어진다. 첫 배달을 받은 날부터 하루도 거르지 않고 고향 음식을 먹을 수 있는 최대 일수를 구하라.

입력

첫 줄에 테스트 케이스의 수 TT가 주어진다. 이어서 TT개의 테스트 케이스가 주어진다. 각 테스트 케이스의 첫 줄에는 가진 돈 MM, 배달비 FF, 음식의 종류 수 NN이 공백으로 구분되어 주어진다. 다음 NN개의 줄에는 음식 한 종류의 한 끼 가격 PiP_i와 신선도 SiS_i가 주어진다.

제한

  • 1≤T≤501 \le T \le 50
  • 1≤F≤M≤10181 \le F \le M \le 10^{18}
  • 1≤N≤2001 \le N \le 200
  • 1≤Pi≤M1 \le P_i \le M
  • 0≤Si≤10180 \le S_i \le 10^{18}

출력

각 테스트 케이스마다 "Case #x: y" 형식으로 한 줄씩 출력한다. xx는 1부터 시작하는 테스트 케이스 번호이고, yy는 하루도 거르지 않고 고향 음식을 한 끼 이상 먹을 수 있는 최대 일수다.

노트

예제 입력의 첫 번째 테스트 케이스에서 3일을 채우는 방법은 다음과 같다. 도시에서 보내는 첫날에 1번 음식 한 끼와 2번 음식 한 끼를 주문한다. 배달비까지 모두 20이 든다. 첫날에 1번 음식을 먹고 다음 날에 2번 음식을 먹는다. 셋째 날에 1번 음식 한 끼를 다시 주문해 그날 바로 먹는다.

예제1

  1. 예제 1

    입력
    3
32 5 2
5 0
10 2
10 10 1
10 10
10 1 1
1 5
    예상 출력
    Case #1: 3
Case #2: 0
Case #3: 8