Ngày nay, robot có thể lái ô tô, nhưng liệu chúng có thể tổ chức một bữa tiệc ra trò không? Nghiên cứu của đội Code Jam về chủ đề này vẫn đang ở giai đoạn đầu. Chúng tôi vừa triển khai \(R\) robot mua hàng đến siêu thị địa phương để mua đồ dùng cho Vòng Chung kết Thế giới tại Toronto, nhưng mô hình bậc nhất của chúng về một bữa tiệc kiểu Canada rất đơn giản: chúng chỉ mua \(B\) “bit” (mỗi bit là một món ăn nhỏ giống bánh vòng có ở vùng này). Chúng tôi sẽ cải thiện trí tuệ nhân tạo của chúng sau; còn bây giờ, chúng tôi muốn giúp chúng mua đủ số bit đó nhanh nhất có thể.

Siêu thị có \(C\) thu ngân có thể quét hàng của khách. Thu ngân thứ \(i\) sẽ:

• nhận tối đa \(M_i\) món hàng từ mỗi khách;
• mất \(S_i\) giây để quét mỗi món;
• mất thêm \(P_i\) giây để xử lý thanh toán và đóng gói các bit.

Nói cách khác, một khách mang \(N\) bit đến thu ngân thứ \(i\) (với \(N\le M_i\)) sẽ tương tác với thu ngân đó tổng cộng \(S_i\times N+P_i\) giây.

Trước khi các robot tương tác với bất kỳ thu ngân nào, bạn có thể phân phối các bit cho robot theo cách tùy ý. (Các bit phải được giữ nguyên; bạn không thể bẻ chúng thành những phần lẻ!) Robot nào không nhận bit sẽ không được tương tác với thu ngân và sẽ thất vọng bỏ đi.

Sau đó, với mỗi robot có ít nhất một bit, bạn chọn cho nó đúng một thu ngân khác nhau. (Hai robot không thể dùng chung một thu ngân, và một robot không thể dùng nhiều hơn một thu ngân.) Tất cả robot bắt đầu tương tác với thu ngân của mình tại thời điểm 0. Lưu ý rằng sau khi một robot tương tác xong với thu ngân, nó không thể được giao thêm bit và cũng không thể tương tác với thu ngân khác.

Nếu bạn giúp các robot đưa ra lựa chọn tối ưu, thời điểm sớm nhất mà tất cả robot có thể hoàn tất tương tác với các thu ngân là khi nào?

Dữ liệu vào

Dòng đầu tiên chứa số lượng bộ test \(T\). Tiếp theo là \(T\) bộ test. Mỗi bộ bắt đầu bằng một dòng gồm ba số nguyên \(R\), \(B\) và \(C\): lần lượt là số robot mua hàng, số bit và số thu ngân. Sau đó có thêm \(C\) dòng. Dòng thứ \(i\) trong số này mô tả thu ngân thứ \(i\) và chứa ba số nguyên \(M_i\), \(S_i\), \(P_i\): số bit tối đa, thời gian quét mỗi bit (tính bằng giây), và thời gian thanh toán/đóng gói (tính bằng giây) của thu ngân đó như đã mô tả ở trên.

Dữ liệu ra

Với mỗi bộ test, in một dòng Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là thời điểm sớm nhất (tính bằng giây) mà tất cả robot có thể hoàn tất tương tác với các thu ngân.

Ràng buộc

• \(1\le T\le100\).
• \(1\le M_i\le10^9\) với mọi \(i\).
• \(1\le S_i\le10^9\) với mọi \(i\).
• \(1\le P_i\le10^9\) với mọi \(i\).
• Tổng của \(R\) giá trị \(M_i\) lớn nhất không nhỏ hơn \(B\). (Tồn tại ít nhất một tập con gồm \(R\) thu ngân có thể xử lý toàn bộ số bit.)

Phân nhóm

Test Set 1 (Hiển thị):

• \(1\le R\le C\le5\).
• \(1\le B\le20\).

Test Set 2 (Ẩn):

• \(1\le R\le C\le1000\).
• \(1\le B\le10^9\).

Điểm các phân nhóm

Mỗi Test Set tương ứng với một subtask trên LQDOJ. Bảng dưới đây giữ nguyên điểm chính thức của Google Code Jam và quy đổi tỷ lệ trên tổng điểm của bài.

Ví dụ

3
2 2 2
1 2 3
1 1 2
2 2 2
1 2 3
2 1 2
3 4 5
2 3 3
2 1 5
2 4 2
2 2 4
2 5 1

Case #1: 5
Case #2: 4
Case #3: 7

Nguồn

Google Code Jam 2018, Vòng 1A, bài Bit Party.

Nguồn chính thức trên Google Coding Competitions Archive, phát hành theo giấy phép Apache-2.0.