Tình hình kinh tế tại thành phố Quy Nhơn ngày càng phát triển. Sau một năm làm việc vất vả và chi tiêu hợp lí, nhiều người dân tại thành phố Quy Nhơn đã tích góp được một số tiền nhất định. Nắm bắt được thời cơ này, ngân hàng X đã tung ra rất nhiều chương trình khuyến mãi để thu hút người dân gửi tiết kiệm.

Giả sử có ~n~ khách hàng đang xếp hàng gửi tiền vào ngân hàng X. Số tiền mà mỗi khách hàng muốn gửi lần lượt là ~a_1~, ~a_2~,..., ~a_n~. Với mỗi khách hàng, nhân viên ngân hàng phải tốn thời gian là 1 phút để hoàn tất thủ tục hồ sơ. Vì cuối năm, các khách hàng rất bận và họ chỉ có thể chờ trong một khoảng thời gian nhất định mà thôi, sau khoảng thời gian đó họ sẽ đi và không gửi tiền ở ngân hàng X nữa. Thời gian mà các khách hàng có thể chờ lần lượt là ~t_1~, ~t_2~, ..., ~t_n~ (tính theo phút).

Giám đốc ngân hàng X muốn làm sao để có được nhiều tiền gửi vào ngân hàng mình nhất. Bạn hãy giúp ông ta đưa ra kế hoạch cho nhân viên lựa chọn thứ tự gửi tiền của các khách hàng sao cho số tiền ngân hàng có được là nhiều nhất (có thể phải chấp nhận từ chối một số khách hàng để đạt được mục đích). Cho:

Input:

• Dòng thứ nhất là số nguyên ~n~ (1 ≤ ~n~ ≤ 10000)
• Trong n dòng tiếp theo, dòng thứ ~i~ gồm hai số nguyên ~a_i~ và ~t_i~ (1 ≤ ~a_i~ ≤ ~10^5~, 0 ≤ ~t_i~ ≤ 1000).

Output:

• Là số nguyên xác định tổng số tiền nhiều nhất có thể thu được.

Ví dụ

Input

4
10 1
20 2
5 2
12 0

Output

42

Input

3
10 0
20 1
5 1

Output

30

Giới hạn:

• 60% số test có ~n~ ≤ 20, 0 ≤ ~t_i~ ≤ 100.
• 40% số test còn lại có ~n~ ≤ 10000 , 0 ≤ ~t_i~ ≤ 1000.