Bạn đang điều hành một doanh nghiệp thành công, kiếm tiền bằng cách hoàn thành công việc cho khách hàng. Hiện có \(N\) công việc mà bạn có thể lựa chọn, được đánh số từ \(1\) đến \(N\). Mỗi công việc chỉ có thể thực hiện một lần.

Hoàn thành công việc \(i\) mang lại lợi nhuận \(x_i\) euro. Lợi nhuận cũng có thể âm, tức là \(x_i<0\).

Một số công việc phụ thuộc vào một công việc khác: có thể có công việc mang số hiệu \(p_i\) phải được hoàn thành trước khi bắt đầu công việc \(i\). Vì thế, một công việc có lợi nhuận lớn có thể không hấp dẫn như vẻ ngoài nếu nó phụ thuộc vào một công việc có lợi nhuận âm. Nếu \(p_i=0\), công việc \(i\) không phụ thuộc vào công việc nào.

Hiện bạn có \(s\) euro. Bạn được quyết định những công việc sẽ thực hiện và thứ tự thực hiện chúng, miễn là tuân thủ các quan hệ phụ thuộc. Ngoài ra, số tiền bạn có không được âm tại bất kỳ thời điểm nào.

Hãy tính lợi nhuận lớn nhất có thể thu được khi chọn thực hiện một số công việc trong \(N\) công việc theo một thứ tự do bạn quyết định. Bạn cũng có thể không thực hiện công việc nào.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(s\), lần lượt là số công việc và số tiền ban đầu bạn có.

Tiếp theo là \(N\) dòng. Dòng thứ \(i\) chứa hai số nguyên \(x_i\) và \(p_i\), lần lượt là lợi nhuận và số hiệu công việc phải hoàn thành trước công việc \(i\). Nếu \(p_i=0\), công việc \(i\) không phụ thuộc vào công việc nào.

Dữ liệu ra

In ra một số nguyên duy nhất là lợi nhuận lớn nhất bạn có thể thu được.

Ràng buộc

• \(1\le N\le 3\cdot 10^5\).
• \(0\le s\le 10^{18}\).
• \(-10^9\le x_i\le 10^9\) với mọi \(1\le i\le N\).
• \(0\le p_i<i\) với mọi \(1\le i\le N\).

Phân nhóm

1. \(11\) điểm: \(s=10^{18}\).
2. \(14\) điểm: \(N\le 2000\) và với mọi \(1\le i\le N\), \(p_i=0\) hoặc \(p_i=i-1\).
3. \(15\) điểm: với mọi \(1\le i\le N\), \(p_i=0\) hoặc \(p_i=i-1\).
4. \(29\) điểm: \(N\le 2000\).
5. \(31\) điểm: không có ràng buộc bổ sung.

Ví dụ

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

6