Alice and Bob are playing an interstellar development game. There are $n$ planets in the game, numbered $1$ to $n$. The mineral reserve on planet $u$ is $w_u$.

To move between different planets, the Interstellar Company has built $n-1$ star gates, following these rules: Each planet $u \in \{2, \dots, n\}$ has exactly one star gate. Specifically, given $p_2, p_3, \dots, p_n$, the star gate on planet $u$ leads to planet $p_u$. Star gates are one-way and cannot be traversed in reverse. Starting from any planet, one can reach planet $1$ through the star gates, where the interstellar market is located.

Bob has $k$ mining ships. He can deploy these mining ships to $k$ different planets. A mining ship can move along the star gates and collect all mineral reserves on the planets along its path (a planet may be passed by multiple mining ships, but its minerals can only be collected once). Finally, the ship arrives at planet $1$ to sell all the collected minerals.

However, before Bob starts mining, a star gate maintenance event is triggered. The Interstellar Company decides to update the layout of the star gates by demolishing $t$ star gates and rebuilding $t$ star gates, such that the structure of the star gates still satisfies the rules. Due to game mechanics, $t$ can be any integer in the range $[0, n-1]$, meaning the star gates might not be updated at all.

After spending some diplomatic points, the task of demolishing the star gates was outsourced to Alice, and the task of rebuilding them was outsourced to Bob. After the rebuilding is complete, Bob deploys his mining ships to mine.

Bob wants to maximize the total amount of minerals he collects, while Alice wants to minimize the total amount of minerals Bob collects. On top of this, Alice wants to demolish as many star gates as possible. Assuming both parties play optimally, find the total amount of minerals Bob collects, and the maximum number of star gates Alice can demolish under that condition.

Input

The input contains multiple test cases. The first line contains a positive integer $T$, representing the number of test cases.

For each test case: The first line contains two positive integers $n, k$. The second line contains $n$ positive integers $w_1, w_2, \dots, w_n$, representing the mineral reserves on each planet. * The third line contains $n-1$ positive integers $p_2, p_3, \dots, p_n$, representing the planet that the star gate on planet $u$ initially leads to.

Output

For each test case, output a single line containing two non-negative integers, representing the total amount of minerals Bob collects, and the maximum number of star gates Alice can demolish while minimizing Bob's mining total.

Examples

Input 1

3
3 1
1 1 1
1 1
7 2
5 8 8 5 8 2 3
1 2 3 4 1 4
16 4
2 7 9 7 9 5 10 10 2 10 5 2 7 6 9 4
1 1 3 3 1 6 5 8 3 10 2 7 8 9 3

Output 1

2 0
37 2
87 4

Note

• In the first test case, if Alice demolishes the star gate of planet $2$, Bob can rebuild it to $p_2 = 3$, so he only needs to place the single mining ship on planet $2$ to collect all $3$ units of minerals from the three planets. The situation where Alice demolishes the star gate of planet $3$ is similar. Therefore, Alice has to demolish no star gates, which allows Bob to have a maximum mining total of $2$.
• In the second test case, one valid strategy for Alice is to demolish the star gates of planets $2$ and $3$.

Constraints

Let $\sum n$ denote the sum of $n$ over all test cases in a single test file. For all test cases, it is guaranteed that: $1 \le T \le 10^4$; $1 \le k \le n \le 2 \times 10^5$, $1 \le \sum n \le 5 \times 10^5$; $1 \le u \le n$, $1 \le w_u \le 10^9$; $2 \le u \le n$, $1 \le p_u \le u-1$.

Special Property A: $k = 1$. Special Property B: $\forall 2 \le u \le n$, $p_u = 1$ or $u-1$.