Mining Strategy

The cg army has discovered a city with abundant mineral resources. The city is modeled as a rooted tree with n nodes numbered 1 to n (with the property that for every non‐root node v every ancestor of v has a number strictly less than v). Each node represents a mining point and each edge represents a street.

You have m subordinates at your disposal. For each mining point i, if you assign j subordinates there, you will obtain T_i,j units of minerals. The values T_i,j (for j = 0,1,…,m) are given in a table.

The allowed mining region is defined by a pair of mining points (u, v) with the guarantee that v is an ancestor of u (note: here an ancestor includes the node itself). You are allowed to distribute your subordinates arbitrarily among the nodes in the control area, which is the subtree rooted at u. In addition, consider the exploration path defined as the unique simple path from u to v; if u ≠ v the path excludes u and includes v, and if u = v the path is just {u}. On the exploration path you are allowed to choose at most one mining point to assign subordinates. (Assigning 0 subordinates is allowed.)

Your total profit is the sum of the minerals obtained from each mine where you assign some subordinates. You must decide how to distribute at most m subordinates among the allowed mines to maximize the profit.

Note: When u ≠ v the two sets – the control area (the subtree rooted at u) and the exploration path – are disjoint. When u = v the node u appears in both sets; however, the restriction means that if you assign a positive number of subordinates to u (which lies on the exploration path) then no other node on the exploration path (in this case, only u) can have a positive assignment.

inputFormat

The first line contains two integers n and m (1 ≤ n, m ≤ 100), the number of nodes and the number of subordinates.

The second line contains two integers u and v (1 ≤ v ≤ u ≤ n) with the guarantee that v is an ancestor of u in the tree.

The third line contains n-1 integers. For i = 2 to n, the i-th number is the parent of node i. It is guaranteed that for every node i (i ≥ 2) the parent is less than i.

Then follow n lines. The i-th of these lines contains m+1 integers: T_i,0, T_i,1, …, T_i,m, where T_i,j is the profit obtained when assigning j subordinates to mining point i. (It is possible that T_i,0 is nonzero.)

outputFormat

Output a single integer, the maximum total profit obtainable under the rules.

sample

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

6