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.|

AL_28_07 - Kontroler biletów

Jaś zatrudnił się ostatnio jako kontroler biletów. Jeździ on pociągiem i sprawdza pasażerom bilety w trakcie przejazdów między stacjami. W czasie pobytu pociągu na stacji Jaś zawsze musi znajdować się na początku pociągu, czyli na początku pierwszego wagonu. Gdy pociąg ruszy może zacząć iść w kierunku końca pociągu i sprawdzać bilety pasażerom lub ich nie sprawdzać i po prostu iść, jednak zawsze gdy pociąg zatrzymuje się na stacji Jaś musi być z powrotem na początku pierwszego wagonu, czyli w pewnym momencie musi zacząć wracać. Oczywiście nawet podczas wracania może sprawdzać bilety. Gdy Jaś sprawdza bilety jest w stanie sprawdzić i jednocześnie przebyć 1 wagon w 2 minuty, a gdy nie sprawdza biletów jest w stanie przebyć 1 wagon w 1 minutę. Jaś w sytuacji w której nie zdąży sprawdzić biletów w jakimś wagonie nie sprawdza w tym wagonie biletów, póki nie jest pewny, że zdąży.

Jaś zna rozkład pociągu i wie ile minut będą trwały kolejne przejazdy między stacjami. Wie również w ilu wagonach pociągu powinien sprawdzić pasażerom bilety. Zastanawia się teraz w ile najmniej przejazdów między stacjami uda się Jasiowi sprawdzić wszystkie bilety jeśli zastosuje odpowiednią taktykę. Pomóż mu!

Wejście

Wielkość jednego pliku testowego nie przekracza 5 MB.

W pierwszej linii liczba zestawów danych T (1 ≤ T ≤ 105).

W pierwszej linii zestawu danych znajdują się dwie liczby całkowite N, M (1 ≤ N ≤ 105, 1 ≤ M ≤ 106) opisujące kolejno ilość przejazdów między stacjami oraz ilość wagonów w których Jaś powinien sprawdzić bilety.

W drugiej linii zestawu danych znajduje się N liczb naturalnych opisujących długości w minutach kolejnych przejazdów między stacjami. Liczby te są nie większe niż 106.

Wyjście

Dla każdego zestawu danych należy wypisać liczbę będącą najmniejszą ilością przejazdów między stacjami potrzebną Jasiowi do sprawdzenia biletów, lub "NIE" jeśli nie jest to możliwe.

Przykład

Wejście:
4
10 1
2 2 2 2 2 2 2 2 2 2
5 3
7 2 3 5 8
2 3
6 7
2 3
6 10
Wyjście:
NIE
4
2
2

Wyjaśnienie do ostatniego przykładu:

W czasie pierwszego przejazdu między stacjami Jaś nic nie robi :)

W czasie drugiego przejazdu Jaś sprawdza bilety w pierwszych trzech wagonach co zajmuje mu łącznie 6 minut. Następnie wraca na początek pierwszego wagonu co zajmuje mu kolejne 3 minuty. Łącznie 9 minut, więc wyrabia się w czasie.


Dodane przez:Bartek
Data dodania:2016-06-16
Limit czasu wykonania programu:1s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.