Mô tả và yêu cầu

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 n 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 ti đơ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: đọc từ file văn bản DIEUDONG.INP gồm:
- 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 ci, ti (ti ≤ 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.
* Ví dụ: ghi ra file văn bản DIEUDONG.OUT một số nguyên duy nhất là thời
điểm sớm nhất tìm được.

* Ví dụ:
DIEUDONG.INP DIEUDONG.OUT
5 10
5 10
3 10
3 20
2 9
2 15
* Ràng buộc: 50% số tests ứng với 50% số điểm của bài có n ≤ 100.