Cho thuê xe

View as PDF

Submit solution


Points: 0.38 (partial)
Time limit: 4.5s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
PreVOI Hải Phòng
Problem type
Allowed languages
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch

Giáo sư ~X~ có một kỳ nghỉ kéo dài ~n~ ngày đánh số từ ~1~ tới ~n~. Ô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 ~n~ chiếc xe cho thuê. Ngày thứ ~i~, người ta chỉ cho thuê chiếc xe thứ ~i~, thời gian thuê từ đầu ngày thứ ~i~ tới hết ngày ~t_i~ ~(t_i \geq i)~ với giá thuê là ~p_i~, tức là nếu vào ngày ~i~ giáo sư ~X~ trả ~p_i~ đồng để thuê chiếc xe thứ ~i~, ông ta phải trả lại nó không muộn hơn ngày ~t_i~ 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

Input

  • Dòng ~1~ chứa số nguyên dương ~n \leq 5~. ~10^{5}~
  • ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên dương ~t_i~, ~p_i~ ~(i \leq t_i \leq n~; ~p_i \leq 10^{6})~ cách nhau ít nhất một dấu cách.

Output

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

Giới hạn

  • Ít nhất ~50\%~ số điểm ứng với các test có ~n \leq 10^{3}~
  • Ít nhất ~75\%~ số điểm ứng với các test có ~n \leq 10^{5}~

Sample Input

4
3 10
3 20
4 1
4 40

Sample Output

11

Comments

Please read the guidelines before commenting.


There are no comments at the moment.