Khám phá vũ trụ

Tí và Tèo là hai phi hành gia của trung tâm vũ trụ Quốc Tế. Họ đang tham gia một sứ mệnh quan trọng: khám phá các hành tinh xa xôi để thu thập năng lượng phục vụ cho Trái đất.

Có $n$ hành tinh được đánh số từ $1$ đến $n$ mà Tí và Tèo có thể hạ cánh. Khi khám phá hành tinh thứ $i$, họ sẽ thu được $x_i$ đơn vị năng lượng nếu $x_i>0$ hoặc sẽ mất đi $|x_i|$ đơn vị năng lượng nếu $x_i<0$ do điều kiện khắc nghiệt. Mỗi hành tinh được khám phá nhiều nhất một lần.

Tuy nhiên, không phải hành tinh nào cũng có thể đến ngay lập tức. Một số hành tinh chỉ có thể hạ cánh sau khi đã khám phá xong một hành tinh khác. Cụ thể, với mỗi hành tinh thứ $i$ có tham số $p_i$ ($0\le p_i<i$), nếu $p_i=0$ hành tinh $i$ có thể khám phá bất kỳ lúc nào mà không phụ thuộc vào hành tinh khác, ngược lại nếu $p_i\ne 0$ thì muốn đến hành tinh $i$, họ phải đến hành tinh $p_i$ trước.

Ban đầu, con tàu vũ trụ của Tí và Tèo có $s$ đơn vị năng lượng. Trong suốt hành trình, năng lượng trên tàu không bao giờ được âm. Mục tiêu của họ là khám phá một số hành tinh (theo một thứ tự tùy chọn) sao cho tổng lượng năng lượng thu được, tức là năng lượng cuối cùng trừ đi $s$, là lớn nhất có thể. Họ có thể không khám phá hành tinh nào, khi đó lượng năng lượng thu được là $0$.

Yêu cầu: Hãy lập trình giúp Tí và Tèo tính toán lượng năng lượng tối đa mà họ có thể thu được sau chuyến khám phá các hành tinh.

Dữ liệu vào

• Dòng 1: Chứa hai số nguyên $n,s$ ($1\le n\le 3\times {10}^5$; $0\le s\le {10}^9$).
• Dòng thứ $i$ trong $n$ dòng sau mỗi dòng gồm hai số nguyên $x_i,p_i$ ($|x_i|\le {10}^9$; $0\le p_i<i$; $i=1,2,\dots ,n$).

Dữ liệu ra

In ra một số nguyên duy nhất là năng lượng tối đa có thể thu được.

Ràng buộc

• $1\le n\le 3\times {10}^5$; $0\le s\le {10}^9$.
• $|x_i|\le {10}^9$; $0\le p_i<i$.

Subtasks

Điểm được tính theo từng test.

• Subtask 1 ($13\%$ số test): $s={10}^9$.
• Subtask 2 ($14\%$ số test): $n\le 2000$; $p_i=0$ hoặc $p_i=i-1$ với mọi $i=1\dots n$.
• Subtask 3 ($16\%$ số test): $p_i=0$ hoặc $p_i=i-1$ với mọi $i=1\dots n$.
• Subtask 4 ($26\%$ số test): $n\le 2000$.
• Subtask 5 ($31\%$ số test): không có ràng buộc gì thêm.

Ví dụ