Supervisors

Dario's company is facing a particularly hard task. To tackle it, Dario plans to select a task force of $K$ people in the best way possible. The choice will be influenced by the company's highly hierarchical tree-like structure.

There are $N$ employees, numbered from $0$ to $N-1$. For each $1 \le i \le N-1$, employee $i$ has a $\text{manager} \ P_i$, where $P_i < i$. Dario, who is employee number $0$, has no direct manager. We say that employee $i$ is a $\text{supervisor}$ of employee $j$ if either $i = j$ or $i$ is the manager of a supervisor of $j$. Note that this is a recursive definition. The $\text{coordinator}$ of a pair of employees $i$ and $j$ is their lowest common ancestor in the company's hierarchy tree, i.e. the employee with the highest identifying number among those that supervise both $i$ and $j$. This is well defined because Dario supervises everyone in the company.

Task

Moreover, each employee has a skill level $S_i$. The $\text{cumulative skill level}$ of a subset of employees $T_0, T_1, \ldots, T_{k - 1}$ is defined as the sum of the skill level of the coordinator of $T_i$ and $T_j$ over all pairs $0 \le i < j < k$.

What is the maximum cumulative skill level that a task force of $K$ people can obtain?

Input data

The input file consists of:

• a line containing integers $N, K$.
• a line containing the $N$ integers $S_{0}, \, \ldots, \, S_{N-1}$.
• a line containing the $\mathtt{N - 1}$ integers $P_{1}, \, \ldots, \, P_{N - 1}$.

Output data

The output file must contain a single line consisting of 64-bit integer $\mathtt{ans}$.

Constraints and clarifications

• $1 \le N \le 2 \ 000$.
• $2 \le K \le N$.
• $1 \le S_i \le 1 \ 000 \ 000 \ 000$ for each $i=0\ldots N-1$.
• $0 \le P_i < i$ for each $i=1\ldots N-1$.

Example 1

stdin

5 3
4 2 5 1 3
0 0 1 1

stdout

12

Explanation

In the first sample case, the maximum cumulative skill level obtainable with a task force of $3$ people is $12$.

One possible way to achieve that is to choose employees $0$, $2$ and $3$. By doing this:

• Employee $0$ and $2$'s coordinator is employee $0$, with a skill level of $4$.
• Employee $0$ and $3$'s coordinator is employee $0$, with a skill level of $4$.
• Employee $2$ and $3$'s coordinator is employee $0$, with a skill level of $4$.

Example 2

stdin

10 5
5 9 4 4 8 9 9 8 7 3
0 0 1 3 4 0 4 0 7

stdout

84