Ủy ban Olympic Tin học Nhật Bản có một hệ thống cấp bậc 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. Mỗi thành viên có một giá trị thể hiện mức độ nhiệt tình của mình.

Ủy ban sắp triển khai một dự án mới. Sự thành công của dự án được cho là phụ thuộc vào tổng mức độ nhiệt tình của những người tham gia, chứ không phụ thuộc vào số người tham gia.

Chủ tịch đã làm \(m\) cuốn sách nhỏ giải thích chi tiết về dự án. Mỗi người tham gia bắt buộc phải đọc sách và bất kỳ ai đọc sách đều phải tham gia dự án.

Ban đầu, chủ tịch giữ cả \(m\) cuốn. Chủ tịch và mỗi người nhận được ít nhất một cuốn sẽ đọc sách trước, rồi chuyển sách cho cấp dưới nếu có. Cấp dưới của một người là những người có cấp trên trực tiếp là người đó. Mỗi cuốn sách có thể được chuyển cho một cấp dưới. Có thể đưa nhiều cuốn cho cùng một cấp dưới, và cũng có thể có cấp dưới không nhận được cuốn nào. Sau khi đọc, một người không cần giữ lại cuốn sách nào cho mình.

Yêu cầu

Cho cấp trên trực tiếp và mức độ nhiệt tình của mỗi người, cùng số sách \(m\), hãy tìm tổng mức độ nhiệt tình lớn nhất của những người tham gia dự án.

Dữ liệu vào

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

• Dòng đầu chứa hai số nguyên \(n,m\), là số thành viên của ủy ban và số cuốn sách.
• Trong \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(s_i,a_i\), nghĩa là người \(i\) có cấp trên trực tiếp là người \(s_i\) và mức độ nhiệt tình là \(a_i\). Giá trị \(s_i=0\) cho biết người \(i\) là chủ tịch.

Các số trên cùng một dòng cách nhau bởi dấu cách. Cấp trên luôn có số hiệu nhỏ hơn cấp dưới, và người \(1\) là chủ tịch.

Dữ liệu ra

Ghi ra đầu ra chuẩn một số nguyên là tổng mức độ nhiệt tình lớn nhất của những người tham gia.

Ràng buộc

• \(1\le n\le10\,000\).
• \(1\le m\le1000\).
• \(0\le s_i<i\), \(1\le a_i\le10\,000\) với \(1\le i\le n\).
• Chỉ có một chủ tịch; mọi người khác đều có đúng một cấp trên trực tiếp.
• Giới hạn thời gian: \(2\) giây cho mỗi test.
• Giới hạn bộ nhớ: \(256\) MB.

Phân nhóm

Bài có \(20\) nhóm chấm, mỗi nhóm gồm đúng một test: lần lượt là 01, 02, ..., 20. Mỗi nhóm được \(5\) điểm nếu trả lời đúng, tổng cộng \(100\) điểm.

Các test tương ứng với \(50\%\) tổng số điểm thỏa mãn \(n\le500\) và \(m\le100\).

Ví dụ

5 2
0 10
1 3
2 5
2 2
1 4

22