POLSKI SPOJ

Zbieranie pieniędzy na cele charytatywne nie jest łatwe. Ludzie rzadko biorą udział w takich akcjach, jeżeli się ich do tego nie zachęci. W związku z tym postanowiłem odwiedzić n moich znajomych w ustalonej przeze mnie kolejności i przekonać ich do wsparcia fundacji Rak'n'Roll. Osoba odwiedzona jako i-ta wesprze moją zbiórkę automatycznie, jeżeli wcześniej wpłaty dokonało co najmniej d_i osób. W przeciwnym wypadku mam do wyboru dwie możliwości:

1. Ruszyć w dalszą drogę
2. Przekonać tę osobę żeby dokonała wpłaty i dopiero wtedy ruszyć w dalszą drogę

Odpowiedz na pytanie, ile minimalnie osób będę musiał przekonać żeby co najmniej m osób dokonało wpłaty?

Wejście

W pierwszej linii wejścia znajduje się liczba zestawów danych t ∈ [1, 710000]. W kolejnych 2×t liniach znajdują się zestawy danych.

Pierwsza linia zestawu danych zawiera dwie liczby całkowite n ∈ [1, 10⁵] i m ∈ [1, n] oznaczające odpowiednio liczbę znajomych, których planuję odwiedzić oraz minimalną liczbę wpłat jaką chcę uzyskać.

W drugiej linii zestawu danych znajduje się n liczb całkowitych z przedziału [0, 2×n]. Liczba i-ta w kolejności określa wartość d_i osoby, którą odwiedzę jako i-tą.

Gwarantujemy, że suma wartości n ze wszystkich zestawów danych nie przekracza 5×10⁶.

Wyjście

Dla każdego zestawu danych należy w osobnej linii wypisać odpowiedź na pytanie, ile minimalnie osób będę musiał przekonać żeby co najmniej m osób dokonało wpłaty.

Przykład

Wejście:

4
8 5
10 5 1 4 2 3 10 4
5 5
3 3 3 3 3
5 2
6 2 5 3 4
5 5
1 2 3 4 5

Wyjście:

1
3
2
5

Wyjaśnienie do przykładu:

W pierwszym zestawie danych wystarczy przekonać osobę 1 albo 2. Wtedy osoby 3, 5, 6 i 8 wpłacą pieniądze automatycznie.