Annie là tài xế xe buýt với công việc đầy căng thẳng. Cô từng thử thư giãn bằng một chuyến du thuyền Caribe, nhưng chuyến đi đó cũng hóa ra căng thẳng, nên gần đây cô chuyển sang cưỡi ngựa.

Hôm nay, Annie cưỡi ngựa về phía đông trên một con đường một chiều dài và hẹp chạy từ tây sang đông. Hiện cô ở kilômét 0 và đích nằm tại kilômét \(D\); các cột kilômét được đánh số tăng dần từ tây sang đông.

Có \(N\) con ngựa khác đang đi về phía đông trên cùng con đường. Tất cả sẽ tiếp tục đi mãi mãi và hiện đều nằm giữa ngựa của Annie với đích. Con thứ \(i\) ban đầu ở kilômét \(K_i\) và đi với tốc độ tối đa \(S_i\) km/h.

Ngựa rất lịch sự: một con \(H_1\) sẽ không vượt (đi lên trước) con \(H_2\) vốn xuất phát phía trước nó. Hai hay nhiều con có thể ở cùng vị trí trong bất kỳ khoảng thời gian nào; có thể xem ngựa là các điểm. Những con ngựa khác Annie đi ở tốc độ tối đa, trừ khi một con nhanh \(H_1\) bắt kịp một con chậm \(H_2\) phía trước; khi đó \(H_1\) giảm tốc để bằng \(H_2\).

Ngựa của Annie không có tốc độ tối đa và có thể đi với bất kỳ tốc độ nào cô chọn, miễn là không vượt con ngựa khác. Để hành trình êm ái cho cả hai, Annie muốn chọn một tốc độ “ga tự động” không đổi duy nhất cho toàn bộ quãng đường từ vị trí hiện tại tới đích, sao cho ngựa của cô không vượt bất kỳ con nào. Tốc độ lớn nhất cô có thể chọn là bao nhiêu?

Dữ liệu vào

Dòng đầu chứa số lượng bộ test \(T\). Mỗi bộ test bắt đầu bằng hai số nguyên \(D,N\): vị trí đích chung của các con ngựa (km) và số ngựa khác trên đường. Tiếp theo là \(N\) dòng; dòng thứ \(i\) chứa \(K_i,S_i\), vị trí ban đầu (km) và tốc độ tối đa (km/h) của con ngựa thứ \(i\).

Dữ liệu ra

Với mỗi bộ test, in Case #x: y, trong đó x là số thứ tự bộ test (bắt đầu từ 1), còn y là tốc độ không đổi lớn nhất (km/h) Annie có thể dùng mà không vượt ngựa khác. y được coi là đúng nếu sai số tuyệt đối hoặc tương đối không quá \(10^{-6}\).

Ràng buộc

• \(1\le T\le100\).
• \(0<K_i<D\le10^9\) với mọi \(i\).
• \(K_i\ne K_j\) với mọi \(i\ne j\); không hai con ngựa nào xuất phát cùng vị trí.
• \(1\le S_i\le10000\).

Phân nhóm

• Test Set 1 (Visible): \(1\le N\le2\).
• Test Set 2 (Hidden): \(1\le N\le1000\).

Đ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
2525 1
2400 5
300 2
120 60
60 90
100 2
80 100
70 10

Case #1: 101.000000
Case #2: 100.000000
Case #3: 33.333333

Nguồn

Google Code Jam 2017, Vòng 1B, bài Steed 2: Cruise Control.

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