HIREHP - Cho thuê xe

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

Ghi chú: Các bài VNOI đã được chuyển qua VNOJ (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 VNOJ. Bạn vẫn có thể tìm kiếm đề bài trên VNOI.

Link đọc đề trên VNOJ

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

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≥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≤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≤t_i≤n;p_i≤ 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

Example 

Input:
4
3 10
3 20
4 1
4 40


Output:
11 
  • Ít nhất 50% số điểm ứng với các test có n≤10^3
  • Ít nhất 75% số điểm ứng với các test có n≤10^5

  • Người up: voj
  • Nguồn bài: PreVOI Hải Phòng