Trường đại học giao thông vận tải tổ chức kỳ nghỉ cho sinh viên giỏi OLP kéo dài n ngày đánh số từ 1 tới n.

Đến địa điểm du lịch, bạn An không muốn đi bộ cùng mọi người nên có ý định thuê xe đạp để đi cho đỡ mỏi chân. Dịch vụ du lịch có đúng n chiếc xe đạp cho thuê.

Nếu thuê xe vào ngày thứ i thì thời gian sử dụng xe từ 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 bạn An trả \(p_i\) đồng để thuê chiếc xe thứ i, bạn ấy phải trả lại nó không muộn hơn ngày \(t_i\) và khi bạn ấy đã trả lại chiếc xe đang thuê mới được phép thuê một chiếc xe khác.

Bạn hãy giúp bạn An 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

Ví dụ

Input:

5
3 10
5 18
4 5
4 9
5 20

Output:

28

Giải thích Bạn được thuê xe từ ngày 1 đến ngày 3 và hết 10 tiền, ngày 2 đến ngày 5 hết 18 tiền, ngày 3 đến ngày 4 hết 5 tiền, ngày 4 đến 4 hết 9 tiền, ngày 5 đến ngày 5 hết 20 tiền để có xe sử dụng đầy đủ 5 ngày tốn tiền để thuê cái xe vào ngày 1 và ngày 2 hết tổng cộng 18 tiền.