GSPVH có sở thích đi mua sắm mỗi khi tan học về. Ngoài trà sữa, GS còn thích mua rất nhiều loại đồ ăn khác nữa, nhưng chỉ có đồ ăn mà thôi!

Siêu thị BigC hôm nay bán \(n\) món ăn, món ăn thứ \(i\) có giá là \(c_i\) đồng. GS chỉ được mua mỗi món ăn tối đa một lần. Do là học sinh giàu vượt sướng, GS chỉ muốn tiêu tối đa \(b\) đồng, dù GS có tới \(10^9\) mol đồng.

Hôm nay siêu thị bigC đưa ra một chương trình khuyến mãi hấp dẫn: Với món ăn thứ \(i\), thay vì mua với giá \(c_i\) ban đầu, khách mua có thể trả ít hơn \(d_i\) đồng. Tuy nhiên, chương trình này đi kèm ràng buộc: Với mỗi món ăn \(i > 1\), có một món ăn \(p_i < i\) mà nếu khách hàng muốn mua món ăn \(i\) với giá ưu đãi, họ bắt buộc phải mua món ăn \(p_i\) cũng với giá ưu đãi. Hệ quả là, họ có thể cũng phải mua tiếp món ăn \(p_{p_i}\) cũng với giá ưu đãi...

Hãy giúp GSPVH tìm ra số món ăn tối đa có thể mua mà không vượt quá hạn mức chi tiêu đã đề ra.

Input

• Dòng đầu tiên chứa hai số nguyên \(n\) và \(b\) \((1 \leq n \leq 5000, 1 \leq b \leq 10^9)\)~--- số món ăn được bán tại siêu thị BigC và hạn mức chi tiêu của GSPVH.
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên \(c_i\) và \(d_i\) \((1 \leq d_i < c_i \leq 10^9)\) - mức giá ban đầu của món ăn thứ \(i\) và số tiền được giảm nếu mua món ăn thứ \(i\) với giá ưu đãi. Nếu \(i > 1\), dòng này sẽ có thêm số nguyên \(p_i\) \((1 \leq p_i \leq i - 1\) cho biết món ăn cần được mua với giá ưu đãi nếu chọn mua món ăn thứ \(i\) cũng với giá ưu đãi.

Output

• Gồm một dòng duy nhất là số món ăn nhiều nhất GSPVH có thể mua với \(b\) đồng.

Scoring

• Subtask \(1\): (\(25\) điểm): \(n \leq 20\).
• Subtask \(2\): (\(30\) điểm): \(n, b \leq 300\).
• Subtask \(3\): (\(45\) điểm): Không có ràng buộc gì thêm.

Example

6 16
10 9
10 5 1
12 2 1
20 18 3
10 2 3
2 1 5

4