A company hierarchy can be represented as a tree. Every $i$ employee has a manager $P_i$, except for the boss $1$.
The company has a new project, if employee $i$ spends $j$ money, the reputation of the company increases by $A_{i,j}$.
The employee $i$ doesn't want the total spending of his subordinates and himself exceed $S_i \le L$. What is the maximum amount of reputation the company can gain?
### Input
- The first line contains 2 integers $n, L$.
- The second line contains contains $n - 1$ integers $p_i$ with $2 \le i \le n$.
- The third line contains $n$ integers $S_i$.
- The next $n$ lines, each line contains $L + 1$ integers $A_{i,0},...,A_{i,L}$.
### Output
- Print the maximum amount of reputation the company can gain.
### Constraints
- $1 \le n, L \le 500$.
- $1 \le p_i \le n$.
- $0 \le S_i \le L$.
- $0 \le A_{i, j} \le 10^6$.
### 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
```
