Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

RNR_01_04 - Wpłaty

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 di 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, 105] 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ść di osoby, którą odwiedzę jako i-tą.

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

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.


Dodane przez:Maciej Boniecki
Data dodania:2019-02-22
Limit czasu wykonania programu:1s-3s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All
Pochodzenie:Rak n Roll

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.