비트 파티

요즘 로봇은 자동차를 운전할 수 있지만, 좋은 파티를 열 수 있을까요? 이 주제에 대한 Code Jam 팀의 연구는 아직 초기 단계입니다. 우리는 $R$대의 로봇 쇼핑객을 지역 슈퍼마켓에 보내 토론토에서 열리는 World Finals 파티 용품을 사 오게 했습니다. 그런데 로봇들이 그린 캐나다 파티의 1차 모델은 아주 단순했습니다. 지역에서 파는 작은 도넛 모양 간식인 "비트"를 $B$개만 샀습니다. AI는 나중에 개선할 예정이지만, 지금은 로봇들이 그 비트를 모두 가능한 한 빨리 사도록 돕고자 합니다.

슈퍼마켓에는 고객의 상품을 스캔하는 계산원이 $C$명 있습니다. $i$번째 계산원은 다음과 같이 동작합니다.

• 고객 한 명당 최대 $M_i$개의 상품을 받습니다.
• 상품 하나를 스캔하는 데 $S_i$초가 걸립니다.
• 결제와 포장에 추가로 $P_i$초가 걸립니다.

즉, $N$개의 비트를 가져온 고객은 ($N$은 $M_i$ 이하여야 합니다) $i$번째 계산원과 총 $S_i \times N + P_i$초 동안 응대를 받습니다.

로봇이 계산원을 이용하기 전에, 비트를 로봇들에게 원하는 대로 나누어 줄 수 있습니다. 비트는 온전해야 하므로 조각으로 쪼갤 수 없습니다. 비트를 하나도 받지 못한 로봇은 계산원을 이용하지 못하고 실망한 채 돌아갑니다.

그다음, 비트를 하나 이상 받은 각 로봇에게 서로 다른 계산원을 한 명씩 고르게 합니다. 두 로봇이 같은 계산원을 쓸 수 없고, 로봇 한 대가 계산원을 둘 이상 쓸 수도 없습니다. 모든 로봇은 시간 0에 계산원과의 응대를 시작합니다. 로봇이 계산원과의 응대를 마치면 비트를 더 받을 수 없고, 다른 계산원과도 응대할 수 없습니다.

로봇들이 최적의 선택을 한다면, 모든 로봇이 계산원과의 응대를 끝낼 수 있는 가장 이른 시각은 언제입니까?

첫 줄에는 테스트 케이스의 수 $T$가 주어집니다. 이어서 $T$개의 테스트 케이스가 주어집니다. 각 테스트 케이스는 로봇 쇼핑객 수 $R$, 비트 수 $B$, 계산원 수 $C$를 나타내는 정수 세 개가 적힌 줄로 시작합니다. 그다음 $C$개의 줄이 주어지며, $i$번째 줄에는 $i$번째 계산원의 최대 비트 수 $M_i$, 비트 하나당 스캔 시간 $S_i$(초), 결제와 포장 시간 $P_i$(초)가 정수 세 개로 적혀 있습니다.

각 테스트 케이스마다 Case #x: y 형식으로 한 줄을 출력합니다. $x$는 1부터 시작하는 테스트 케이스 번호이고, $y$는 모든 로봇이 계산원과의 응대를 끝낼 수 있는 가장 이른 시각(초)입니다.

• $1 \le T \le 100$.
• 모든 $i$에 대해 $1 \le M_i \le 10^9$.
• 모든 $i$에 대해 $1 \le S_i \le 10^9$.
• 모든 $i$에 대해 $1 \le P_i \le 10^9$.
• $M_i$ 값 중 가장 큰 $R$개의 합은 $B$ 이상입니다. (계산원 $R$명으로 모든 비트를 처리할 수 있는 경우가 적어도 하나 있습니다.)

예제 1에서는 로봇이 2대, 비트가 2개, 계산원이 2명이며, 각 계산원은 상품을 한 개만 처리할 수 있습니다. 따라서 비트를 로봇마다 하나씩 줘야 합니다. 1번 계산원은 5초, 2번 계산원은 3초가 걸리므로 필요한 시간은 5초입니다.

예제 2는 앞의 경우와 비슷하지만, 이번에는 2번 계산원이 최대 2개까지 처리할 수 있습니다. 따라서 비트를 모두 한 로봇에게 주고, 그 로봇이 2번 계산원을 이용하게 하는 것이 가장 좋습니다. 상품 하나당 1초에 2초를 더해 4초가 걸립니다.

예제 3에서 최적의 전략은 비트 2개를 가진 로봇 한 대를 2번 계산원에게 보내고, 비트를 하나씩 가진 로봇 두 대를 나머지 계산원 중 아무 곳에나 보내는 것입니다.