H. Capital Logistics
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

The kingdom consists of $$$n$$$ cities forming a tree rooted at the capital (city $$$1$$$). For each city $$$i$$$ ($$$2 \le i \le n$$$), its parent is $$$p_i$$$. Each city $$$i$$$, including the capital, stores $$$a_i$$$ units of goods that must be collected by the royal transport system.

Each day, the royal transport system operates as follows:

  • A convoy can collect goods from a set of cities, including the capital city itself.
  • Due to road constraints, the convoy can collect from a city $$$C_i$$$ only if no other city on the path from the capital to $$$C_i$$$ is selected on the same day.
  • From each selected city, exactly $$$1$$$ unit of goods is collected.

Before transport begins, you may discard up to $$$k$$$ units of goods in total from any combination of cities to simplify logistics.

Your task is to determine the minimum number of days required to transport all remaining goods to the capital.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Then the description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$k$$$ ($$$1 \le n \le 2 \cdot 10^5$$$, $$$0 \le k \le 10^{18}$$$) — the number of cities and the maximum number of goods that can be discarded.

The second line of each test case contains $$$n-1$$$ integers $$$p_2, p_3, \dots, p_n$$$ ($$$1 \le p_i \lt i$$$), where $$$p_i$$$ is the parent of city $$$i$$$.

The third line contains $$$n$$$ integers $$$a_1, a_2, \dots, a_n$$$ ($$$0 \le a_i \le 10^9$$$) — the amount of goods stored in each city.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, print a single integer — the minimum number of days required to transport all remaining goods to the capital.

Example
Input
3
2 3
1
1 2
4 0
1 1 1
1 0 0 0
3 2
1 1
2 1 2
Output
0
1
2
Note

In the first test case, we can discard all goods before transport begins, so the answer is $$$0$$$.

In the second test case, no goods can be discarded. Since only city $$$1$$$ contains goods, the convoy needs exactly $$$1$$$ day.

In the third test case, we can discard $$$2$$$ units of goods from city $$$1$$$. Then, on the first day, the convoy collects $$$1$$$ unit from city $$$2$$$ and city $$$3$$$ each, and on the second day, it collects $$$1$$$ remaining unit from city $$$3$$$. Thus, the answer is $$$2$$$.