Bob's new favourite toy is a rooted tree that consists of n vertices numbered from 1 to n. The number of the root vertex is 1. The tree has l leafs (the root is not considered to be a leaf). Each leaf of the tree has an integer written in it.
This birthday Bob received n - l stickers as a gift: k of them are labelled "min", and the other n - l - k are labelled "max". Bob has decided to place the stickers on the internal vertices of the tree, a single sticker on each internal vertex.
Once he has placed all the stickers on the tree, Bob would like to calculate a function f for each vertex v of the tree in the following fashion:
Bob isn't yet sure how to place his stickers on the tree, but he is interested in the value of f in the root vertex. Given the tree and the stickers, help Bob calculate the minimum and the maximum possible value of f(1)!
The first line contains two space-separated integers n and k (2 ≤ n ≤ 105, 0 ≤ k ≤ n). The second line contains n - 1 space-separated integer numbers p2, p3, ..., pn (1 ≤ pi ≤ n). The number pi denotes the parent of the vertex numbered i. The third line contains n space-separated integer numbers a1, a2, ..., an (0 ≤ ai ≤ 109). If the vertex i is a leaf, then ai is the number written in that vertex. Otherwise ai will be equal to 0.
It is guaranteed that the given graph will be a tree. It is guaranteed that k + l ≤ n.
In a single line output two integers separated by a space — the minimum and the maximum possible value of f(1).
A #cf_span(class=[tex-font-style-underline], body=[tree]) is a connected graph that has no cycles. A rooted tree is a tree with one vertex being the #cf_span(class=[tex-font-style-underline], body=[root vertex]). In a rooted tree, a vertex u is a #cf_span(class=[tex-font-style-underline], body=[child]) of v if and only if there is an edge between v and u, and u does not belong to the path that connects the root vertex with v. The vertex v then is called the #cf_span(class=[tex-font-style-underline], body=[parent]) of u. A vertex of a rooted tree is called a #cf_span(class=[tex-font-style-underline], body=[leaf]) if and only if it has no children. Otherwise the vertex is called an #cf_span(class=[tex-font-style-underline], body=[internal vertex]).
## Input
The first line contains two space-separated integers n and k (2 ≤ n ≤ 105, 0 ≤ k ≤ n). The second line contains n - 1 space-separated integer numbers p2, p3, ..., pn (1 ≤ pi ≤ n). The number pi denotes the parent of the vertex numbered i. The third line contains n space-separated integer numbers a1, a2, ..., an (0 ≤ ai ≤ 109). If the vertex i is a leaf, then ai is the number written in that vertex. Otherwise ai will be equal to 0.It is guaranteed that the given graph will be a tree. It is guaranteed that k + l ≤ n.
## Output
In a single line output two integers separated by a space — the minimum and the maximum possible value of f(1).
[samples]
## Note
A #cf_span(class=[tex-font-style-underline], body=[tree]) is a connected graph that has no cycles. A rooted tree is a tree with one vertex being the #cf_span(class=[tex-font-style-underline], body=[root vertex]). In a rooted tree, a vertex u is a #cf_span(class=[tex-font-style-underline], body=[child]) of v if and only if there is an edge between v and u, and u does not belong to the path that connects the root vertex with v. The vertex v then is called the #cf_span(class=[tex-font-style-underline], body=[parent]) of u. A vertex of a rooted tree is called a #cf_span(class=[tex-font-style-underline], body=[leaf]) if and only if it has no children. Otherwise the vertex is called an #cf_span(class=[tex-font-style-underline], body=[internal vertex]).
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of vertices in a rooted tree with root at vertex 1.
Let $ l = |\{ i \in \{1, \dots, n\} \mid \text{vertex } i \text{ is a leaf} \}| $ be the number of leaves.
Let $ k \in \mathbb{Z} $, $ 0 \leq k \leq n $, be the number of "min" stickers; the remaining $ n - l - k $ stickers are "max".
Let $ P = (p_2, p_3, \dots, p_n) $, where $ p_i $ is the parent of vertex $ i $, defining the tree structure.
Let $ A = (a_1, \dots, a_n) $, where $ a_i \in \mathbb{Z}_{\geq 0} $: if vertex $ i $ is a leaf, $ a_i $ is its value; otherwise $ a_i = 0 $.
Let $ I = \{ i \in \{1, \dots, n\} \mid \text{vertex } i \text{ is internal} \} $, so $ |I| = n - l $.
Let $ S_{\text{min}} \subseteq I $, $ |S_{\text{min}}| = k $, be the set of internal vertices assigned "min" stickers.
Let $ S_{\text{max}} = I \setminus S_{\text{min}} $, $ |S_{\text{max}}| = n - l - k $, be the set assigned "max" stickers.
Define function $ f(v) $ recursively:
- If $ v $ is a leaf, $ f(v) = a_v $.
- If $ v $ is internal:
- If $ v \in S_{\text{min}} $, then $ f(v) = \min_{u \in \text{children}(v)} f(u) $.
- If $ v \in S_{\text{max}} $, then $ f(v) = \max_{u \in \text{children}(v)} f(u) $.
**Constraints**
1. $ 2 \leq n \leq 10^5 $
2. $ 0 \leq k \leq n $
3. $ k + l \leq n $
4. Tree is valid: parent array defines a rooted tree with root 1.
5. Leaf values: $ 0 \leq a_i \leq 10^9 $ for leaf $ i $; $ a_i = 0 $ for internal $ i $.
**Objective**
Compute:
$$
\min_{S_{\text{min}} \subseteq I,\, |S_{\text{min}}| = k} f(1) \quad \text{and} \quad \max_{S_{\text{min}} \subseteq I,\, |S_{\text{min}}| = k} f(1)
$$