Giải bài trực tuyến

Austin và Agrron vừa đào được một túi gồm N thỏi kim loại quý. Thỏi thứ k chứa A[k] gram vàng và B[k] gram bạc. Họ muốn chia phần trước khi chia tay nhau, nhưng có một vài rắc rối xảy ra. Đó là Austin chỉ quan tâm đến vàng, trong khi Agrron chỉ quan tâm đến bạc (với 1 người thích vàng, bao nhiêu bạc cũng là vô nghĩa và ngược lại). Sau khi chia xong, ngay lập tức họ sẽ loại bỏ phần kim loại họ không thích (phần này người kia không thể lấy được).

Để đảm bảo công bằng, họ có thể tách một số thỏi kim loại ra thành 2 phần. Với mỗi thỏi, họ có thể tách nó ra theo bất kì tỉ lệ nào, và mỗi người có thể chọn phần mình muốn (lưu ý, việc tách thỏi kim loại không làm thay đổi tỉ lệ phân bổ vàng-bạc trong 2 thỏi nhỏ hơn. Chẳng hạn, với 1 thỏi chứa 6 gram vàng và 4 gram bạc, có thể tách nó thành 2 thỏi, mỗi thỏi chứa 3 gram vàng và 2 gram bạc, trong khi không thể tách nó thành 2 thỏi, một thỏi chứa 6 gram vàng và thỏi còn lại chứa 4 gram bạc).

Xác định số gram vàng (bạc) nhiều nhất mà người nhận được ít hơn có thể có sau quá trình trao đổi này, nếu họ chọn phương án tối ưu.

Input

• Dòng đầu tiên chứa một số nguyên N là số thỏi kim loại.
• N dòng tiếp theo, mỗi dòng chứa 2 số nguyên A[i], B[i] là số gram vàng và bạc có trong thỏi thứ i.

Output

• Một dòng duy nhất là đáp số bài toán. Kết quả được chấp nhận nếu chênh lệch không quá 10^-6 so với đáp số tối ưu.

Giới hạn

• 0 < N ≤ 100000.
• 0 ≤ A[i],B[i] ≤ 1000.
• Trong 20% số test, chỉ có đúng 1 viên đá có lẫn cả vàng và bạc (tức là trong N – 1 viên, A[i] = 0 hoặc B[i] = 0).

Example

Input:
2
10 3
6 10

Output:
10.000

Giải thích: Austin lấy thỏi thứ nhất và Agrron lấy thỏi thứ hai, mỗi người được 10 gram có ích. Các đáp số 9.999999 hoặc 10.000001 cũng được chấp nhận.

Input:
1
30 15

Output:
10.0

Giải thích: Tách thỏi kim loại theo tỉ lệ 1/3 và 2/3. Austin lấy phần nhỏ hơn (có 1/3 * 30 = 10 gram vàng), thỏi kia thuộc về Agrron (có 2/3 * 15 = 10 gram bạc).