Apple Tree Happiness

Consider a rooted tree with n nodes, numbered from 1 to n, where node 1 is the root and for every node i > 1 its parent has a smaller index. Each node i contains a_i > 0 apples. Taking one apple from node i yields v_i > 0 units of happiness. In other words, if you take k apples from node i (with k ≤ a_i), you gain k*v_i happiness.

However, there is a restriction: if you take at least one apple from a node, then you must also take at least one apple from its parent. Hence, the set of nodes from which at least one apple is taken forms a connected subtree that necessarily contains the root (if nonempty).

In addition, you are given a positive integer k. Suppose you take a total of t apples and the maximum depth among the nodes where you took apples is h (the root has depth 1). These numbers must satisfy the inequality \[ t - h \le k. \] The goal is to choose how many apples to take from some nodes (possibly all, subject to the restrictions) so as to maximize the overall happiness.

Note: For each node that you take apples from, you must take at least one apple. However, if a node lies on the chosen root-to-leaf path that reaches the deepest level among all chosen nodes, then the mandatory apple taken at that node does not count towards t in the inequality t - h \le k (i.e. it is free). Formally, if we define x_i as the number of apples taken at node i (with 0 meaning no apple is taken), then if we denote by D a root-to-leaf path (with depth h) contained in the chosen subtree, the constraint can be rewritten as \[ \sum_{i: x_i>0} x_i - |D| \le k,\] where we must have x_i \ge 1 for every node in the chosen subtree and |D| = h (since every node on the main (discount) chain contributes one free apple).

Input Format: The first line contains two integers n and k. The second line contains n integers, where the i-th integer is a_i. The third line contains n integers, where the i-th integer is v_i. The fourth line contains n-1 integers; the i-th integer (for i=2,...,n) is the parent of node i (which is guaranteed to be less than i).

Output Format: Output a single integer representing the maximum happiness that can be achieved.

inputFormat

The input begins with a line containing two integers n and k.

The second line contains n positive integers: a₁, a₂, ..., a_n.

The third line contains n positive integers: v₁, v₂, ..., v_n.

The fourth line contains n-1 integers: for each i = 2,...,n an integer p_i denoting the parent of node i.

outputFormat

Output one integer, the maximum total happiness achievable under the given conditions.

sample

3 1
1 1 1
1 2 3
1 1

6