POLSKI SPOJ

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 ≤ 10⁵).

W pierwszej linii zestawu danych znajdują się dwie liczby całkowite N, M (1 ≤ N ≤ 10⁵, 1 ≤ M ≤ 10⁶) 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ż 10⁶.

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.