Sau khi thực thi quy hoạch của Bộ Giao thông, sơ đồ giao thông của thành phố H gồm n tuyến đường ngang và n tuyến đường dọc cắt nhau tạo thành một lưới ô vuông với n x n nút giao thông. Các nút giao thông được gán tọa độ theo hàng từ 1 đến n, từ trên xuống dưới và theo cột từ 1 đến n, từ trái sang phải. Ban chỉ đạo an toàn giao thông quyết định điều động cảnh sát giao thông đến các nút giao thông làm nhiệm vụ. Ban đầu mỗi cảnh sát được phân công đứng trên một nút của một tuyến đường ngang khác nhau. Đến giờ cao điểm, xuất hiện ùn tắc tại các tuyến đường dọc không có cảnh sát giao thông. Để sớm giải quyết tình trạng này, Ban chỉ đạo an toàn giao thông quyết định điều động một số cảnh sát giao thông ở một số nút, từ nút hiện tại sang một nút khác cùng hàng ngang để đảm bảo mỗi tuyến đường dọc đều có mặt của cảnh sát giao thông.

Yêu cầu

Biết rằng cảnh sát ở hàng ngang thứ ~i~ cần ~t_i~ đơn vị thời gian để di chuyển qua 1 cạnh của lưới ô vuông (~i = 1, 2,..., n~), hãy giúp Ban chỉ đạo an toàn giao thông tìm cách điều động các cảnh sát thỏa mãn yêu cầu để đạt ra sao cho việc điều động được hoàn thành tại thời điểm sớm nhất. Giả thiết là các cảnh sát được điều động đồng thời thực hiện việc di chuyển đến vị trí mới tại thời điểm 0.

Input

• Dòng thứ nhất chứa một số nguyên dương n (~n ≤ 10000~).
• Dòng thứ i trong số n dòng tiếp theo chứa hai số nguyên dương ~c_i, t_i~ (~t_i ≤ 10000~) tương ứng là tọa độ cột và thời gian để di chuyển qua 1 cạnh của lưới ô vuông của cảnh sát đứng trên tuyến đường ngang thứ i (~i = 1, 2,..., n~). Hai số trên cùng một dòng được ghi cách nhau ít nhất một dấu cách.

Output

Một số nguyên duy nhất là thời điểm sớm nhất tìm được.

Sample Test

Input

5
5 10
3 10
3 20
2 9
2 15

Output

10

Ràng buộc

~50\%~ số tests ứng với ~50\%~ số điểm của bài có ~n ≤ 100~