JOI có \(N\) dây treo trang trí để gắn vào điện thoại di động, được đánh số từ \(1\) đến \(N\). Cậu muốn chọn một số dây treo trong số đó để gắn vào điện thoại.

Những dây treo của JOI hơi đặc biệt: một số dây có các đầu nối để gắn thêm những dây treo khác. Mỗi dây treo có thể được gắn trực tiếp vào điện thoại hoặc vào một đầu nối của một dây treo khác. Mỗi đầu nối gắn được một dây treo. Có thể gắn trực tiếp vào điện thoại nhiều nhất một dây treo.

Mỗi dây treo mang lại một mức độ vui thích nhất định khi được gắn vào, được biểu diễn bằng một số nguyên. Có những dây treo mà JOI không thích; mức độ vui thích của chúng là số âm.

JOI muốn tổng mức độ vui thích của các dây treo được nối với điện thoại là lớn nhất. Không nhất thiết phải gắn dây treo vào mọi đầu nối, và cũng có thể không gắn dây treo nào.

Yêu cầu

Cho thông tin về \(N\) dây treo của JOI, hãy viết chương trình tìm tổng mức độ vui thích lớn nhất của các dây treo được nối với điện thoại khi chọn cách gắn phù hợp.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa số nguyên \(N\), là số dây treo.
• Dòng thứ \(i\) trong \(N\) dòng tiếp theo (\(1 \le i \le N\)) chứa hai số nguyên \(A_i\), \(B_i\), cách nhau bởi dấu cách. Dây treo \(i\) có \(A_i\) đầu nối và mang lại mức độ vui thích \(B_i\) khi được gắn vào.

Dữ liệu ra

In ra đầu ra chuẩn một dòng chứa một số nguyên là tổng mức độ vui thích lớn nhất của các dây treo được nối với điện thoại.

Ràng buộc

Mọi dữ liệu vào đều thỏa mãn:

• \(1 \le N \le 2\,000\).
• \(0 \le A_i \le N\) với mọi \(1 \le i \le N\).
• \(-1\,000\,000 \le B_i \le 1\,000\,000\) với mọi \(1 \le i \le N\).

Phân nhóm

• Nhóm 1 (5 điểm): \(N \le 15\)
• Nhóm 2 (5 điểm): \(B_i \ge 0\) với mọi \(1 \le i \le N\)
• Nhóm 3 (45 điểm): \(A_i \le 15\) với mọi \(1 \le i \le N\)
• Nhóm 4 (45 điểm): Không có ràng buộc bổ sung.

Ví dụ

5
0 4
2 -2
1 -1
0 1
0 3

5

6
2 -3
3 -1
0 -4
0 -2
1 -3
4 -1

0

15
1 -4034
1 3406
0 6062
4 -6824
0 9798
0 4500
0 -1915
1 2137
0 9786
0 7330
0 -9365
2 2730
0 -5797
0 6129
0 8925

43417