Cho thuê xe
Xem dạng PDFGiá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
Bình luận
Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.
Mk nghĩ nên dùng segment tree