비트 파티

요즘 로봇은 자동차를 운전할 수 있지만, 멋진 파티도 열 수 있을까? 이 주제에 관한 Code Jam 팀의 연구는 아직 초기 단계에 있다. 우리는 토론토에서 열리는 월드 파이널의 파티 용품을 사기 위해 방금 R대의 쇼핑 로봇을 동네 슈퍼마켓에 보냈지만, 캐나다식 파티에 관한 로봇들의 일차 모델은 매우 단순했다. 로봇들은 B개의 "비트"(이 지역에서 볼 수 있는 도넛 모양의 작은 간식)만 샀다. 로봇들의 AI은 나중에 개선하겠지만, 지금은 로봇들이 그 비트를 모두 최대한 빨리 구매하도록 돕고자 한다.

슈퍼마켓에는 고객의 구매 물품을 스캔할 수 있는 C명의 계산원이 있다. i번째 계산원은 다음과 같이 처리한다.

• 고객 한 명당 최대 $M_{i}$개의 물품을 받는다

• 각 물품을 스캔하는 데 $S_{i}$초가 걸린다

• 결제를 처리하고 비트를 포장하는 데 추가로 $P_{i}$초를 쓴다.

즉, i번째 계산원에게 N개의 비트를 가져가는 고객(N은 $M_{i}$ 이하여야 함)은 그 계산원과 상호작용하는 데 총 $S_{i}$ × N + $P_{i}$초를 쓴다.

로봇들이 어떤 계산원과도 상호작용하기 전에, 원하는 방식으로 비트를 로봇들에게 분배한다. (비트는 온전한 상태로 유지해야 하며, 비트를 분수 단위의 조각으로 쪼갤 수 없다!) 비트를 하나도 받지 못한 로봇은 계산원과 상호작용하지 못하고 실망한 채 떠난다.

그런 다음 비트를 적어도 하나 받은 각 로봇에 대해 서로 다른 계산원 한 명을 선택한다. (두 로봇은 같은 계산원을 이용할 수 없고, 한 로봇은 둘 이상의 계산원을 이용할 수 없다.) 모든 로봇은 시각 0에 계산원과 상호작용하기 시작한다. 로봇은 계산원과의 상호작용을 마친 뒤에는 비트를 더 받을 수 없고 다른 계산원과도 상호작용할 수 없음에 유의한다.

로봇들이 최적의 선택을 하도록 돕는다면, 모든 로봇이 계산원과의 상호작용을 끝낼 수 있는 가장 이른 시각은 언제인가?

제한

1 ≤ T ≤ 100. 모든 i에 대해 1 ≤ $M_{i}$ ≤ $10^{9}$. 모든 i에 대해 1 ≤ $S_{i}$ ≤ $10^{9}$. 모든 i에 대해 1 ≤ $P_{i}$ ≤ $10^{9}$. $M_{i}$의 가장 큰 R개 값의 합은 ≥ B이다. (적어도 하나의 R명 계산원 부분집합은 모든 비트를 처리할 수 있다.) 시간 제한: 테스트 세트당 15초. 메모리 제한: 1GB.

테스트 세트 1 (공개)

1 ≤ R ≤ C ≤ 5. 1 ≤ B ≤ 20.

테스트 세트 2 (비공개)

1 ≤ R ≤ C ≤ 1000. 1 ≤ B ≤ $10^{9}$.

입력의 첫 번째 줄에는 테스트 케이스의 수 T가 주어진다. 이어서 T개의 테스트 케이스가 주어진다. 각 테스트 케이스는 로봇 쇼핑객, 비트, 계산원의 수를 나타내는 세 정수 R, B, C가 있는 한 줄로 시작한다. 그다음 C개의 줄이 더 주어진다. 이 중 i번째 줄은 i번째 계산원을 나타내며, 세 정수 $M_{i}$, $S_{i}$, $P_{i}$이 주어진다. 이들은 위에서 설명한 해당 계산원의 최대 비트 수, 비트당 스캔 시간(초), 결제 및 포장 시간(초)을 나타낸다.

각 테스트 케이스마다 Case #x: y을 포함하는 한 줄을 출력한다. 여기서 x는 테스트 케이스 번호(1부터 시작함)이고, y은 모든 로봇이 계산원과의 상호작용을 마칠 수 있는 가장 이른 시각(초)이다.

예제 케이스 #1에는 두 대의 로봇, 두 개의 비트, 두 명의 계산원이 있으며, 각 계산원은 물품을 하나만 처리할 수 있다. 따라서 각 로봇에게 비트를 하나씩 주어야 한다. 계산원 1은 5초가 걸리고 계산원 2은 3초가 걸리므로, 필요한 시간은 5초이다.

예제 케이스 #2은 이전 경우와 유사하지만, 이제 계산원 2은 최대 2개의 물품을 처리할 수 있다. 따라서 모든 비트를 로봇 한 대에게 주고 그 로봇이 계산원 2을 이용하게 하는 것이 최선이다. 여기에는 물품당 1초에 추가로 2초가 들어, 총 4초가 걸린다.

예제 케이스 #3에서 최적의 전략은 한 대의 로봇이 2개의 비트를 가지고 계산원 2에게 가게 하고, 두 대의 로봇이 각각 1개의 비트를 가지고 나머지 계산원 중 아무에게나 가게 하는 것이다.