Ôi không — cả \(N\) con chim cút nuôi của bạn đều đã sổng mất! Hiện bạn ở vị trí 0 trên một đường thẳng. Con chim thứ \(i\) bắt đầu tại vị trí nguyên khác 0 là \(P_i\) mét trên đường thẳng đó và liên tục chạy ra xa bạn với vận tốc nguyên không đổi \(S_i\) mét mỗi giây. Bạn có thể chạy với vận tốc nguyên không đổi \(Y\) mét mỗi giây và đổi hướng tức thời bất cứ lúc nào. Lưu ý rằng chim cút luôn chạy ra xa bạn, kể cả khi lúc đó bạn không chạy về phía chúng. Bất cứ khi nào bạn và một con chim ở cùng một điểm, con chim ấy được bắt mà không tốn thêm thời gian.

Hãy tìm số giây nhỏ nhất cần để bắt tất cả chim cút.

Dữ liệu vào

Dòng đầu chứa số bộ test \(T\). Mỗi bộ test bắt đầu bằng một dòng gồm hai số nguyên \(Y\) (vận tốc của bạn) và \(N\) (số chim cút), rồi đến hai dòng, mỗi dòng chứa \(N\) số nguyên cách nhau bởi dấu cách. Dòng đầu trong hai dòng này chứa các vị trí \(P_i\) của chim; dòng thứ hai chứa các vận tốc \(S_i\).

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à số giây nhỏ nhất cần để bắt hết chim.

\(y\) được coi là đúng nếu sai số tuyệt đối hoặc tương đối so với đáp án đúng không vượt quá \(10^{-6}\).

Ràng buộc

• \(1\le T\le100\).
• \(2\le Y\le1000\).
• \(-10^7\le P_i\le10^7\) và không có \(P_i\) nào bằng 0.
• \(1\le S_i<Y\).

Phân nhóm

• Tập nhỏ: \(1\le N\le25\).
• Tập lớn: \(1\le N\le500\).

Đ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ụ

2
4 3
-3 -6 -9
3 2 1
2 2
1 -1
1 1

Case #1: 3.000000
Case #2: 5.000000

Nguồn

Google Code Jam 2015, Vòng 3, bài Runaway Quail.

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