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

HIREHP - Cho thuê xe

 

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

Được gửi lên bởi:VOJ Team
Ngày:2012-12-21
Thời gian chạy:3s
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ừ: GOSU PERL6 PYPY RUST SED
Nguồn bài:PreVOI Hải Phòng

hide comments
2017-10-28 10:30:12
{dinh truong lam}

1 dam
2017-09-05 21:36:12
thuật toán:
https://vietcodes.github.io/code/71/
2017-05-30 12:05:38
Stack + Chặt nhị phân => AC
2016-12-08 02:26:33
IT(heap)+DP 1 đấm AC
2016-10-13 11:14:10
Ta có 2 đầu mút, ta có 1 giá trị....Uhm.... Cây IT.
2016-09-21 17:20:49
85 là sao vậy mn =(((
2016-09-10 04:36:40
IT
2016-09-01 15:45:37
trâu 85 :3
2016-06-05 10:46:11
95 lưu ý kết quả là long long nhé (1 số mảng và hằng số cần đặt đủ lớn)
2016-03-20 19:03:31
main 10 dòng và mem 3.4M

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.