Tại một thời điểm gọi là thời điểm ban đầu, những người đua xe đạp tham gia cuộc đua đường trường ở các vị trí cách điểm xuất phát $x_1,x_2,\ldots,x_n$ mét ($n$ là tổng số người đua). Mỗi người di chuyển với vận tốc không đổi riêng của mình; các vận tốc là $v_1,v_2,\ldots,v_n$ mét mỗi giây. Tất cả đều di chuyển cùng một hướng.

Một phóng viên đưa tin về cuộc thi muốn xác định thời điểm khoảng cách giữa người dẫn đầu và người cuối cùng nhỏ nhất, để chụp ảnh tất cả người tham gia cuộc đua cùng lúc từ trực thăng.

Hãy viết chương trình, với số người đua $n$, các vị trí ban đầu $x_1,x_2,\ldots,x_n$ và các vận tốc $v_1,v_2,\ldots,v_n$ đã cho, tính một thời điểm $t$ mà khoảng cách $l$ giữa người dẫn đầu và người cuối cùng nhỏ nhất.

Dữ liệu vào

Dòng đầu tiên của tệp đầu vào chứa số nguyên $n$, là số người đua xe đạp.

Mỗi dòng trong $n$ dòng tiếp theo chứa hai số nguyên: $x_i$, khoảng cách từ điểm xuất phát đến người đua thứ $i$ tại thời điểm ban đầu ($0\le x_i\le10^7$), và $v_i$, vận tốc của người đó ($0\le v_i\le10^7$).

Dữ liệu ra

Ghi hai số thực vào tệp đầu ra: $t$, thời gian tính bằng giây từ thời điểm ban đầu đến khi khoảng cách tính bằng mét giữa người dẫn đầu và người cuối cùng nhỏ nhất, và $l$, khoảng cách đó.

Các số $t$ và $l$ phải có sai số tuyệt đối hoặc tương đối không quá $10^{-6}$. Nghĩa là, nếu số được in là $x$ và đáp án đúng là $y$, đáp án được coi là đúng nếu $|x-y|/\max\{1,|y|\}$ không vượt quá $10^{-6}$.

Ví dụ

Dữ liệu vào 1

3
0 40
30 10
40 30

Dữ liệu ra 1

1 30

Dữ liệu vào 2

5
90 100
100 70
100 70
110 60
120 35

Dữ liệu ra 2

0.5 5.000000000000

Nhiệm vụ con

Bài này có bốn nhiệm vụ con. Mỗi nhiệm vụ con được chấm bằng một nhóm kiểm thử riêng. Chỉ được nhận điểm của nhiệm vụ con khi vượt qua tất cả kiểm thử trong nhóm đó.

Nhiệm vụ con 1 (20 điểm)

$2\le n\le50$, $0\le x_i\le1000$, $0\le v_i\le1000$. Bảo đảm tồn tại một đáp án trong đó $t$ là số nguyên không vượt quá $1000$.

Nhiệm vụ con 2 (20 điểm)

$2\le n\le200$.

Nhiệm vụ con 3 (30 điểm)

$2\le n\le2000$.

Nhiệm vụ con 4 (30 điểm)

$2\le n\le10^5$.

Phản hồi

Trong vòng thi, bạn có thể yêu cầu kết quả chạy chương trình trên các bộ kiểm thử của ban giám khảo tối đa 10 lần. Không được yêu cầu thường xuyên hơn một lần mỗi 5 phút. Với mỗi bộ kiểm thử, kết quả chạy chương trình trên bộ đó sẽ được thông báo.

Trong bài này, bạn có thể chọn lời giải sẽ được chấm điểm. Khi đó, điểm được tính cho lời giải tốt hơn trong các lời giải sau:

• lời giải được chọn rõ ràng;
• lời giải cuối cùng được tiếp nhận để chấm.

Nếu không chọn, lời giải tốt nhất trong các lời giải sau sẽ được chấm:

• các lời giải mà bạn đã xem điểm;
• lời giải cuối cùng được tiếp nhận để chấm.