Ủy ban Olympic Tin học Nhật Bản có cơ cấu cấp trên và cấp dưới rất nghiêm ngặt. Có đúng một chủ tịch; mỗi người khác có đúng một cấp trên trực tiếp. Vì bảo mật, mỗi người chỉ biết cấp trên trực tiếp và các cấp dưới trực tiếp của mình. Không được liên lạc bằng phương tiện điện tử hoặc công cộng, nên những người không biết nhau phải truyền thông tin qua những người quen biết trực tiếp.

Mỗi thành viên có một chỉ số nhiệt tình, có thể âm. Ủy ban muốn chọn ít nhất một người cho một dự án tuyệt mật. Mức độ thành công được đánh giá bằng tổng chỉ số nhiệt tình của những người được chọn. Bất kỳ hai người trong dự án phải liên lạc được với nhau mà không nhờ người ngoài dự án chuyển tiếp.

Biết cấp trên và chỉ số nhiệt tình của mỗi người, hãy tìm tổng chỉ số nhiệt tình lớn nhất của một nhóm hợp lệ.

Dữ liệu vào

Đọc từ đầu vào chuẩn.

Dòng đầu chứa số thành viên \(n\), với \(1 \le n \le 100000\).

Dòng thứ \(i+1\) chứa \(s_i,a_i\), với \(0 \le s_i < i\) và \(-100 \le a_i \le 100\). Người \(i\) có cấp trên là người \(s_i\) và chỉ số nhiệt tình \(a_i\). Giá trị \(s_i=0\) chỉ chủ tịch. Cấp trên luôn có số thứ tự nhỏ hơn cấp dưới.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là tổng chỉ số nhiệt tình lớn nhất.

Chấm điểm

Giới hạn thời gian: \(1\) giây mỗi bộ dữ liệu. Giới hạn bộ nhớ: \(64\) MB.

Có \(20\) bộ dữ liệu, mỗi bộ \(5\) điểm; tổng cộng \(100\) điểm.

Ví dụ

5
0 10
1 5
2 -8
1 -15
4 3

15