#976. HIRE - Thuê xe

Giáo sư X có một kỳ nghỉ kéo dài ngày đánh số từ tới . Ông ta muốn thuê những chiếc mô-tô để đi ngắm cảnh bởi ông muốn thử cảm giác tốc độ giữa quang cảnh hoang dã của thiên nhiên. Dịch vụ du lịch có đúng chiếc xe cho thuê. Ngày thứ , người ta chỉ cho thuê chiếc xe thứ , thời gian thuê từ đầu ngày thứ tới hết ngày với giá thuê là , tức là nếu vào ngày giáo sư X trả đồng để thuê chiếc xe thứ , ông ta phải trả lại nó không muộn hơn ngày và khi ông ta đã trả lại chiếc xe đang thuê mới được phép thuê một chiếc xe khác.

Yêu cầu: Bạn hãy giúp giáo sư X tính xem cần ít nhất bao nhiêu tiền để thuê xe sao cho ngày nào cũng có xe để đi.

Dữ liệu:

• Dòng đầu chứa số nguyên dương ;
• dòng tiếp theo, dòng thứ chứa hai số nguyên dương cách nhau ít nhất một dấu cách.

Kết quả:

• Ghi ra một số nguyên duy nhất là số tiền thuê xe.

Ví dụ:

Dữ liệu:

4
3 10
3 20
4 1
4 40

Kết quả:

11

Giới hạn:

• Ít nhất số điểm ứng với các test có ;
• Ít nhất số điểm ứng với các test có .