Giải bài trực tuyến

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