Trong một môn phái ninja, các ninja được cử đi làm nhiệm vụ cho khách hàng và nhận thù lao theo công việc. Có đúng một ninja là Trưởng môn. Mỗi ninja khác có đúng một cấp trên. Để bảo mật và khuyến khích năng lực lãnh đạo, mọi chỉ thị công việc chỉ được truyền từ cấp trên xuống cấp dưới, có thể qua nhiều người trung gian.

Bạn cần chọn một số ninja để cử đi làm nhiệm vụ. Ninja được cử đi phải được trả mức lương cố định của họ, và tổng lương không được vượt quá ngân sách. Bạn cũng phải chọn một ninja làm quản lý sao cho người này có thể truyền chỉ thị tới mọi ninja được cử đi. Các ninja không được cử đi vẫn có thể làm trung gian truyền chỉ thị. Quản lý có thể được cử đi hoặc không; nếu không được cử đi thì không phải trả lương cho người đó.

Mức độ hài lòng của khách hàng bằng số ninja được cử đi nhân với chỉ số lãnh đạo của quản lý. Hãy tìm mức độ hài lòng lớn nhất có thể đạt được.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên \(N, M\): số ninja và ngân sách.
• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa ba số nguyên \(B_i, C_i, L_i\): cấp trên, mức lương và chỉ số lãnh đạo của ninja \(i\). Nếu \(B_i=0\) thì ninja \(i\) là Trưởng môn.

Luôn có \(B_i<i\), do đó số hiệu cấp trên của một ninja luôn nhỏ hơn số hiệu của ninja đó.

Dữ liệu ra

In ra mức độ hài lòng lớn nhất có thể đạt được.

Ràng buộc

• \(1\le N\le 100\,000\).
• \(1\le M\le 1\,000\,000\,000\).
• \(0\le B_i<i\).
• \(1\le C_i\le M\).
• \(1\le L_i\le 1\,000\,000\,000\).

Ví dụ

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

6

Giải thích

Chọn ninja \(1\) làm quản lý và cử ninja \(3,4\) đi làm nhiệm vụ. Tổng lương là \(4\), không vượt quá ngân sách. Có \(2\) ninja được cử đi và chỉ số lãnh đạo của quản lý là \(3\), nên mức độ hài lòng là \(2\times3=6\). Đây là giá trị lớn nhất.

Phân nhóm

Nguồn

Asia-Pacific Informatics Olympiad 2012, bài Dispatching.