Farmer John phát hiện ra rằng đàn bò của ông cho sữa chất lượng cao hơn khi phải vận động gắng sức. Vì vậy, ông quyết định đưa \(N\) con bò (\(1 \le N \le 25\,000\)) đi leo lên rồi xuống một ngọn núi gần đó!

Con bò thứ \(i\) mất \(U(i)\) đơn vị thời gian để leo lên núi, rồi mất \(D(i)\) đơn vị thời gian để xuống núi. Vì là bò đã được thuần hóa, mỗi con cần một nông dân giúp đỡ trong từng chặng leo; nhưng do tình hình kinh tế khó khăn, chỉ có hai nông dân là Farmer John và người anh em họ Farmer Don. FJ dự định dẫn bò ở chặng lên, sau đó FD sẽ dẫn bò ở chặng xuống. Vì mọi con bò đều cần người dẫn và mỗi chặng chỉ có một nông dân phụ trách, tại bất kỳ thời điểm nào nhiều nhất một con bò được leo lên (với sự hỗ trợ của FJ), và nhiều nhất một con bò được leo xuống (với sự hỗ trợ của FD). Một nhóm bò có thể tạm thời tụ lại trên đỉnh núi nếu chúng đã leo lên nhưng phải chờ FD hỗ trợ mới có thể đi xuống. Thứ tự bò xuống núi có thể khác thứ tự chúng leo lên.

Hãy xác định lượng thời gian ít nhất có thể để cả \(N\) con bò hoàn thành toàn bộ hành trình.

Dữ liệu vào

• Dòng 1 chứa số bò \(N\).
• Các dòng từ 2 đến \(1+N\): dòng \(i+1\) chứa hai số nguyên \(U(i)\) và \(D(i)\) cách nhau bởi dấu cách (\(1 \le U(i), D(i) \le 50\,000\)).

Dữ liệu ra

In một số nguyên duy nhất biểu thị lượng thời gian ít nhất để tất cả các con bò vượt qua ngọn núi.

Ví dụ

3
6 4
8 1
2 3

17

Nguồn

USACO 2012 January Contest, Silver - Mountain Climbing: https://usaco.org/index.php?page=viewproblem2&cpid=108

Tác giả: Videh Seksaria, 2012.