MOVE12 - VOI 2012 Điều động

Giới hạn
  • Thời gian: 0.2s
  • Bộ nhớ: 1536MB
  • Mã nguồn: 50000 bytes

Ghi chú: Các bài VNOI đã được chuyển qua Codeforces (Thông báo). Đề bài trên VNOI và vn.spoj.com sẽ không được cập nhật nữa. Một số đề bài không chính xác sẽ chỉ được cập nhật trên Codeforces. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên Codeforces

 

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 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.

Ràng buộc : 50% số tests ứng với 50% số điểm của bài có n ≤ 100.

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

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

Example

Input:
5
5 10
3 10
3 20
2 9
2 15

Output:
10


  • Người up: voj
  • Nguồn bài: VOI 2012