Công ty

Một công ty có thể được biểu diễn bằng một cây gồm \(n\) nhân viên, đánh số từ \(1\) đến \(n\). Nhân viên \(1\) là giám đốc; mỗi nhân viên \(i\) (\(i \ge 2\)) có đúng một người quản lí trực tiếp \(p_i\) (\(p_i < i\)).

Công ty có một dự án mới: nếu nhân viên \(i\) tiêu \(j\) tiền cho dự án, danh tiếng của công ty tăng thêm \(A_{i,j}\).

Nhân viên \(i\) không muốn tổng số tiền mà anh ta và tất cả cấp dưới (trực tiếp hoặc gián tiếp) của anh ta tiêu cho dự án vượt quá \(S_i\).

Hãy tìm cách chi tiêu hợp lí sao cho tổng danh tiếng công ty tăng thêm là lớn nhất, biết rằng với mọi nhân viên \(i\), tổng số tiền tiêu trong cây con gốc \(i\) (gồm \(i\) và toàn bộ cấp dưới của \(i\)) không được vượt quá \(S_i\).

Input

• Dòng đầu tiên gồm hai số nguyên \(n, L\) (\(1 \le n, L \le 500\)).

• Dòng thứ hai gồm \(n - 1\) số nguyên \(p_2, p_3, \ldots, p_n\) (\(1 \le p_i < i\)), trong đó \(p_i\) là người quản lí trực tiếp của nhân viên \(i\).

• Dòng thứ ba gồm \(n\) số nguyên \(S_1, S_2, \ldots, S_n\) (\(0 \le S_i \le L\)).

• \(n\) dòng tiếp theo, dòng thứ \(i\) gồm \(L + 1\) số nguyên \(A_{i,0}, A_{i,1}, \ldots, A_{i,L}\) (\(0 \le A_{i,j} \le 10^6\)).

Ràng buộc:

• Có \(40\%\) số test thỏa mãn \(n, L \le 100\).

• Có \(60\%\) số test còn lại thỏa mãn \(n, L \le 500\).

Output

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

Example

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

Note

Cây trong ví dụ là một đường thẳng \(1 - 2 - 3 - 4 - 5\) (nhân viên \(1\) quản lí \(2\), \(2\) quản lí \(3\), ..., \(4\) quản lí \(5\)).

Một cách chi tiêu tối ưu: nhân viên \(1, 2, 3, 5\) không tiêu tiền (tiêu \(0\)), nhân viên \(4\) tiêu \(1\) tiền. Khi đó danh tiếng tăng thêm là \(A_{1,0} + A_{2,0} + A_{3,0} + A_{4,1} + A_{5,0} = 5 + 3 + 1 + 1 + 1 = 11\), đồng thời tổng chi phí trong mọi cây con đều không vượt quá \(S_i\) tương ứng.