📘 Mô tả

Công ty được mô hình hoá thành một cây có n nhân viên, gốc là giám đốc 1. Với mỗi nhân viên i (2 ≤ i ≤ n) biết trước người quản lí trực tiếp pi. Công ty nhận một dự án mới: nếu nhân viên i chi j tiền (0 ≤ j ≤ L) thì danh tiếng của công ty tăng Ai,j. Nhân viên i yêu cầu tổng chi phí của chính họ và toàn bộ cấp dưới không vượt quá Si. Hãy tìm mức tăng danh tiếng lớn nhất có thể đạt được.

📥 Input

• Dòng đầu chứa hai số nguyên n, L.
• Dòng thứ hai chứa n - 1 số nguyên pi (2 ≤ i ≤ n).
• Dòng thứ ba chứa n số nguyên Si.
• n dòng tiếp theo, dòng thứ i (tính từ 1) chứa L + 1 số nguyên Ai,0, …, Ai,L.

📤 Output

In ra một số nguyên là mức danh tiếng lớn nhất công ty có thể đạt.

🔒 Ràng buộc

• 1 ≤ n, L ≤ 500
• 1 ≤ pi ≤ n
• 0 ≤ Si ≤ L
• 0 ≤ Ai,j ≤ 106

🧪 Ví dụ

Input:

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

Output:

11