H. Hourly Mate
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

After an unusually high number of reports that the Mate Machine was empty, VIS finally investigated the reasons for this. It turns out that a majority of the purchases were made by a single individual named Sascha. Fortunately, recent advancements in facial recognition technology now make it possible to prevent Sascha from making any more purchases in the future. Instead, they plan to install a separate machine exclusively for him.

Currently, there are $$$n$$$ Mate drinks in the machine, each belonging to some type $$$a$$$. In total, there are $$$m$$$ different types of Mate. Additionally, each Mate drink will expire in $$$b$$$ hours and cannot be sold after that. As a serious Mate addict, Sascha buys and consumes one Mate every hour.

Sascha enjoys every type of Mate equally. However, with this machine, it is not possible to select a specific type of Mate to buy; instead, a carefully designed algorithm decides which of the Mate in the machine to dispense. Assuming the machine dispenses the Mate optimally, what is the biggest integer $$$k$$$ such that Sascha can consume $$$k$$$ Mate of every type?

Input

Each test contains multiple test cases. The first line contains the number of test cases t ($$$1 \le t \le 10^4$$$).

The description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$1 \le n \le 3 \cdot 10^5$$$, $$$1 \le m \le 3 \cdot 10^5$$$) – the number of Mate and the types of Mate there are.

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,...,a_n$$$ ($$$1 \le a_i \le m$$$) — the type of each Mate.

The third line of each test contains $$$n$$$ integers $$$b_1,b_2,...,b_n$$$ ($$$0 \le b_i \le 10^9$$$) — the hours until a Mate expires. Note that if $$$b_i = j$$$, then Mate $$$i$$$ can be up to the $$$j+1$$$'th Mate sold to Sascha. Specifically, if $$$b_i = 0$$$ then this can (only) be the first Mate sold to Sascha.

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

Output

For each test case, output a single line containing an integer: the maximum integer $$$k$$$ such that Sascha can buy $$$k$$$ Mate of each type.

Example
Input
3
5 4
4 2 1 3 2
3 3 1 7 2
4 2
1 2 1 2
0 1 2 3
6 5
4 3 3 3 5 1
4 2 2 1 5 14
Output
1
2
0
Note

In the first test case the machine can first dispense Mate $$$5$$$ (type $$$2$$$), after one hour dispense Mate $$$3$$$ (type $$$1$$$), one hour later Mate $$$4$$$ (type $$$3$$$), and finally Mate $$$1$$$ (type $$$4$$$). As there are exactly $$$4$$$ types of Mate, every type was dispensed once and the answer is $$$1$$$.

In the second test case the machine can dispense in the order $$$1$$$, $$$2$$$, $$$3$$$, $$$4$$$. This is the only optimal dispense order and the answer is $$$2$$$.

In the third test case there is no Mate of type $$$2$$$, hence, the answer is $$$0$$$.