May rủi là một phần quan trọng của cá cược. Một số người tìm hiểu kỹ điều mình đặt cược để tăng cơ hội thắng. Bài toán này xét một cách khác: tận dụng việc nhiều nhà cái đưa ra tỷ lệ cược khác nhau cho cùng một sự kiện.

Sự kiện có hai kết quả có thể xảy ra. Có \(n\) nhà cái. Nhà cái thứ \(i\) đưa ra tỷ lệ \(a_i\) cho kết quả thứ nhất và \(b_i\) cho kết quả thứ hai. Nếu đặt cược \(1\) euro và dự đoán đúng, bạn nhận lại số euro bằng tỷ lệ đã chọn; nếu dự đoán sai, bạn không nhận được gì. Mỗi cược luôn tốn \(1\) euro.

Bạn có thể chọn bất kỳ tập con nào trong các lựa chọn cược được đưa ra, kể cả đặt cược vào cả hai kết quả tại cùng một nhà cái. Tuy nhiên, không được đặt nhiều hơn một cược vào cùng một kết quả tại cùng một nhà cái.

Với mỗi kết quả của sự kiện, lợi nhuận bằng tổng tiền nhận được từ các cược thắng trừ tổng số tiền đã đặt cược. Hãy tìm lợi nhuận được đảm bảo lớn nhất, tức là giá trị lớn nhất mà bạn có thể đảm bảo nhận được bất kể kết quả nào xảy ra.

Dữ liệu vào

Dòng đầu chứa số nguyên \(n\) (\(1\le n\le100000\)), là số nhà cái.

Mỗi dòng trong \(n\) dòng tiếp theo chứa hai số thực \(a_i,b_i\) (\(1.0\le a_i,b_i\le1000.0\)), là tỷ lệ cược cho kết quả thứ nhất và kết quả thứ hai tại nhà cái thứ \(i\). Mỗi số có không quá \(4\) chữ số sau dấu thập phân.

Dữ liệu ra

In lợi nhuận được đảm bảo lớn nhất, làm tròn và hiển thị đúng \(4\) chữ số sau dấu thập phân.

Ví dụ

4
1.4 3.7
1.2 2
1.6 1.4
1.9 1.5

0.5000

Giải thích

Một cách đặt cược tối ưu là cược vào kết quả thứ hai tại nhà cái thứ nhất, và cược vào kết quả thứ nhất tại nhà cái thứ ba và thứ tư. Nếu kết quả thứ nhất xảy ra, lợi nhuận là \(1.6+1.9-3=0.5\) euro. Nếu kết quả thứ hai xảy ra, lợi nhuận là \(3.7-3=0.7\) euro. Vì vậy lợi nhuận được đảm bảo là \(0.5\) euro.

Phân nhóm

1. \(20\) điểm: \(n\le10\).
2. \(40\) điểm: \(n\le1000\).
3. \(40\) điểm: Không có ràng buộc bổ sung.