Konstantin và Ilia sống cùng một nhà. Konstantin sống ở tầng trên và thích các hoạt động nhảy nhót, di chuyển đồ đạc và nói chung là gây tiếng ồn. Ilia sống ở tầng dưới và thích ngủ.

Để có một buổi tối vui vẻ, Konstantin muốn thực hiện ít nhất \(K\) hoạt động. Đêm qua, Ilia đã nhờ Konstantin cố gắng đừng làm anh ấy thức giấc; và vì Konstantin là một người hàng xóm rất tốt, anh ấy đã đồng ý. Tuy nhiên, anh ấy hiểu yêu cầu của Ilia hơi máy móc, và anh ấy sẽ chọn các hoạt động của mình sao cho giảm thiểu xác suất Ilia bị đánh thức sau khi đã ngủ.

Mỗi hoạt động có thể thực hiện của Konstantin có một xác suất đi kèm là \(a_i/b_i\). Nếu Konstantin thực hiện hoạt động này, thì sau khi kết thúc, Ilia sẽ thức với xác suất \(a_i/b_i\), và ngủ trong trường hợp ngược lại, bất kể trước đó anh ấy đang thức hay đang ngủ. Hơn nữa, đối với mỗi hoạt động, Konstantin có thể thực hiện tối đa \(c_i\) lần (nhiều hơn thế sẽ gây nhàm chán, và Konstantin sẽ không có một buổi tối vui vẻ nếu anh ấy thấy chán).

Konstantin muốn chọn một số lượng hoạt động để thực hiện theo thứ tự, sao cho:

• Tổng số hoạt động được thực hiện ít nhất là \(K\).
• Hoạt động thứ \(i\) được thực hiện không quá \(c_i\) lần.
• Xác suất \(Q\) mà Ilia bị đánh thức một hoặc nhiều lần trong suốt quá trình thực hiện các hoạt động là nhỏ nhất có thể.

Ilia bắt đầu ở trạng thái thức, vì vậy để anh ấy bị đánh thức, anh ấy phải đang ngủ ở cuối một hoạt động nào đó, và sau đó thức dậy ở cuối hoạt động tiếp theo.

\(Q\) nhỏ nhất mà Konstantin có thể đạt được trong khi vẫn có một buổi tối vui vẻ là bao nhiêu? Lưu ý rằng Konstantin không thể biết Ilia đang thức hay đang ngủ, vì vậy anh ấy không thể điều chỉnh các hoạt động của mình dựa trên thông tin đó.

Dữ liệu vào

Dòng đầu tiên của đầu vào cho biết số lượng bộ test, \(T\). \(T\) bộ test tiếp theo. Mỗi bộ test bắt đầu bằng một cặp số nguyên \(N, K\) trên một dòng riêng biệt. \(N\) dòng tiếp theo, mỗi dòng đại diện cho một hoạt động mà Konstantin có thể chọn. Mỗi dòng có định dạng a_i/b_i c_i, cho biết có một hoạt động sẽ khiến Ilia thức với xác suất \(a_i/b_i\) và Konstantin có thể thực hiện tối đa \(c_i\) lần mà không bị chán.

Dữ liệu ra

Đối với mỗi bộ test, hãy xuất một dòng chứa Case #x: Q, trong đó \(x\) là số thứ tự bộ test (bắt đầu từ 1) và \(Q\) là xác suất nhỏ nhất Ilia bị đánh thức trong quá trình thực hiện các hoạt động của Konstantin. Các câu trả lời có sai số tuyệt đối hoặc tương đối không lớn hơn \(10^{-6}\) sẽ được chấp nhận.

Ràng buộc

• \(1 \le T \le 100\).
• \(0 \le a_i \le b_i \le 1000000\) với mọi \(i\).
• \(1 \le b_i\) và \(1 \le c_i\) với mọi \(i\).
• \(1 \le K \le\) tổng tất cả các \(c_i\) trong bộ test đó.

Phân nhóm

• Test set 1 (Visible): \(1 \le N \le 100\); Tổng tất cả các \(c_i\) không quá 100.
• Test set 2 (Hidden): \(1 \le N \le 10000\); Tổng tất cả các \(c_i\) không quá \(10^6\).

Đ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
4 1
1/2 3
1/5 2
2/5 1
2/2 2
3 2
1/2 2
1/3 2
3/4 2
3 3
99/100 1
1/2 2
1/50 3

Case #1: 0.000000000
Case #2: 0.083333333
Case #3: 0.015000000

Nguồn

Google Code Jam 2012, Chung kết thế giới, bài Upstairs/Downstairs.

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