Năm học mới, thư viện trường THPT nơi An đang theo học được bổ sung ~n~ (~1 \leq n \leq 10^5~) quyển sách mới.
Mỗi quyển sách có chiều rộng là ~W~ (cm), độ dày là ~T~ (cm).
Các quyển sách được đánh số thứ tự từ 1 đến n.

Do khuôn viên thư viện không đủ diện tích để trưng bày, nên các cuốn sách phải được xếp chồng lên nhau theo quy tắc sau:

• Chỉ được lần lượt chọn từ quyển sách có số thứ tự nhỏ đến lớn (giữ nguyên thứ tự ban đầu, không được hoán đổi vị trí).
• Một quyển sách chỉ có thể đặt lên trên quyển khác nếu chiều rộng của nó không lớn hơn chiều rộng của quyển sách ở dưới.

Chiều cao của chồng sách được tính bằng tổng độ dày của các quyển sách trong chồng.

Hãy tính chiều cao lớn nhất có thể đạt được khi xếp chồng từ ~n~ quyển sách đã cho.

Input

Đọc từ tệp BOOKS.INP:

• Dòng 1: Số nguyên ~n~ — số lượng sách.
• ~n~ dòng tiếp theo: mỗi dòng gồm 2 số nguyên ~W_i, T_i~ lần lượt là chiều rộng và độ dày của quyển sách thứ ~i~ (~1 \leq W_i, T_i \leq 500~).

Output

Ghi ra tệp BOOKS.OUT một số nguyên duy nhất — chiều cao lớn nhất có thể đạt được.

Sample

BOOKS.INP

6
20 3
18 10
19 2
15 7
10 12
9 5

BOOKS.OUT

37

Giới hạn

• 60% số test thỏa mãn ~1 \leq n \leq 10^4~.
• 40% số test thỏa mãn ~10^4 < n \leq 10^5~.