Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

MOVE12 - VOI 2012 Điều động

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.

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

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

Được gửi lên bởi:VOJ Team
Ngày:2012-01-17
Thời gian chạy:0.200s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:Tất cả ngoại trừ: ASM64 GOSU PERL6 PYPY RUST SED
Nguồn bài:VOI 2012

hide comments
2019-07-09 03:31:28
lạ lùng
2019-01-08 18:12:52


Last edit: 2019-01-08 18:13:07
2018-11-26 15:25:12
de hay qua
2018-09-26 06:49:31
à hiểu rồi, điều động đồng thời chứ không phải điều động từng người một
2018-09-26 06:46:37
ai giải thích hộ test đề bài với
2018-01-22 09:50:28
trâu ac caicuccut
2017-12-03 04:16:16
xin code trâu đi
2017-11-08 08:25:02
nhật hào sạch
2017-11-06 13:30:39
khó quá huhu
2017-09-26 05:37:27
trau AC nhé
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.