Huân tước Petir muốn tuyển tổng cộng ~S = a_1 + a_2 + \dots + a_n~ binh lính từ ~n~ tiểu vương quốc.

Từ tiểu vương quốc ~i~ có thể tuyển tối đa ~a_i~ người, mỗi người tuyển (trong điều kiện bình thường) phải trả ~c_i~ đồng vàng. Dữ liệu đảm bảo: nếu ~a_i < a_j~ thì ~c_i < c_j~.

Tuy nhiên có ưu đãi cưỡng bức như sau: tại thời điểm đang làm việc với tiểu vương quốc nào đó, nếu số quân đã tuyển được trước đó là ~x~ mà lớn hơn số người còn lại chưa tuyển ở tiểu vương quốc đó (tức là ~x > r~, với ~r~ là số người còn lại của tiểu vương quốc đó), thì tiểu vương quốc sẽ nộp toàn bộ ~r~ người còn lại miễn phí.

Hãy tính số tiền tối thiểu cần chi để cuối cùng tuyển đủ ~S~ người.

Yêu cầu

Tìm số tiền tối thiểu phải trả để tuyển đủ toàn bộ ~S~ binh lính, với quyền quyết định thứ tự làm việc giữa các tiểu vương quốc và số người trả tiền/mượn miễn phí theo quy tắc trên.

Dữ liệu

• Dòng đầu tiên chứa số nguyên ~n~ (~1 \le n \le 1000~).
• ~n~ dòng tiếp theo, dòng thứ ~i~ chứa hai số nguyên ~a_i, c_i~ (~1 \le a_i \le 100~, ~1 \le c_i \le 10000~).

Dữ liệu đảm bảo: nếu ~a_i < a_j~ thì ~c_i < c_j~.

Kết quả

Ghi ra một số nguyên — số tiền tối thiểu cần chi trả.

Ví dụ

Ví dụ 1

Input

3
1 1
2 2
4 3

Output

5

Giải thích

Ví dụ 1

Tổng cần tuyển ~S = 1 + 2 + 4 = 7~.

Một cách đạt chi phí ~5~:

• Tuyển trả tiền ~1~ người ở nhóm ~c=1~ → đã có ~x=1~.
• Tuyển trả tiền ~2~ người ở nhóm ~c=2~ → đã có ~x=3~.
• Ở nhóm ~a=4~, còn lại ~r=4~ và ~x=3~ không lớn hơn ~r~, nên chưa được miễn phí toàn bộ. Ta trả tiền ~2~ người (tốn ~2 \cdot 3 = 6~) thì không tối ưu.

Nhưng nếu chọn trình tự và cách lấy hợp lý, có thể khiến một phần được nộp miễn phí để đạt tổng chi phí nhỏ nhất là ~5~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le n \le 1000~
• ~1 \le a_i \le 100~
• ~1 \le c_i \le 10000~
• Nếu ~a_i < a_j~ thì ~c_i < c_j~