Tại cửa hàng bánh nổi tiếng X, có \(n\) khách hàng đang xếp hàng mua bánh, được đánh số từ \(1\) đến \(n\) theo đúng thứ tự xếp hàng. Khách hàng thứ \(i\):

• Muốn mua \(a_i\) chiếc bánh.
• Sẵn sàng chờ tối đa \(t_i\) phút.

Thời gian phục vụ mỗi khách hàng là đúng \(1\) phút. Tại mỗi thời điểm, cửa hàng chỉ có thể phục vụ tối đa một khách hàng. Cửa hàng bắt buộc phải phục vụ khách theo đúng thứ tự xếp hàng. Chủ cửa hàng có thể từ chối phục vụ một số khách hàng.

Nếu khách hàng thứ \(i\) không được bắt đầu phục vụ trước hoặc tại thời điểm \(t_i\) thì khách hàng đó sẽ rời đi và không mua hàng.

Yêu cầu: Hãy xác định tổng số bánh lớn nhất mà cửa hàng có thể bán được.

Input

• Dòng \(1\) ghi số nguyên dương \(n\) (\(1 \le n \le 10^4\)).
• \(n\) dòng tiếp theo, dòng thứ \(i\) ghi hai số nguyên \(a_i, t_i\) (\(1 \le a_i \le 10^5, 0 \le t_i \le 10^4\)).

Output

• Ghi ra một số nguyên duy nhất là tổng số bánh lớn nhất có thể bán được.

Example

6
8 0
50 2
10 1
40 3
30 3
100 5

220

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(1 \le n \le 1000, 0 \le t_i \le 1000\).
• Subtask \(2\) (\(30\%\) số điểm): \(1 \le n \le 5000, 0 \le t_i \le 5000\).
• Subtask \(3\) (\(40\%\) số điểm): \(1 \le n \le 10^4, 0 \le t_i \le 10^4\).