Minh có n viên gạch, viên gạch thứ i có khối lượng wᵢ và giá trị vᵢ. Cậu muốn chọn ra một số viên gạch để xếp thành một tòa tháp từ dưới lên trên, sao cho với mỗi viên gạch trong tháp, tổng khối lượng của tất cả các viên gạch phía trên nó không được vượt quá giá trị của chính nó.

Cậu muốn biết tổng giá trị lớn nhất của tòa tháp xếp được (tức tổng giá trị của tất cả các viên gạch trong tháp) là bao nhiêu.

Dữ liệu vào

Dữ liệu vào gồm $n+1$ dòng:

• Dòng đầu tiên là một số nguyên dương $n$, biểu thị số lượng viên gạch.

• $n$ dòng sau, mỗi dòng gồm hai số nguyên dương $w_i, v_i$, lần lượt biểu thị khối lượng và giá trị của mỗi viên gạch.

Dữ liệu ra

In ra một số nguyên biểu thị tổng giá trị lớn nhất.

Ví dụ

Input

5
4 4
1 1
5 2
5 5
4 3

Output

10

Ghi chú

Giải thích ví dụ

Chọn các viên gạch thứ 1, 2, 4, xếp thành một tòa tháp theo thứ tự 2, 1, 4 từ trên xuống dưới, tổng giá trị là $4+1+5=10$.

Quy mô và ràng buộc dữ liệu chấm

• Với 20% dữ liệu, đảm bảo $n \le 10$;

• Với 100% dữ liệu, đảm bảo $n \le 1000$, $w_i \le 20$, $v_i \le 20000$.