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_02_05 - Przeprowadzka

Bajteusz jest wielkim fanem Eulera. Kolekcjonuje wszystkie przedmioty związane ze swoim idolem. Oprócz wszystkich jego prac jest on w posiadaniu niewyobrażalnej ilości rzeczy osobistych wielkiego matematyka - od marynarki po jego szczoteczkę do zębów.

Ostatnio Bajteusz wygrał mieszkanie w konkursie na zapamiętanie i odtworzenie największej ilości grafów planarnych. Pozostało się zatem przeprowadzić, a co za tym idzie spakować do pudełek wszystkie eksponaty z kolekcji. Na szczęście Bajteusz ma kolegę w fabryce pudełek, więc ma ich do dyspozycji nawet do 2.37*∞. Jednak nie chcąc niepotrzebnie wykorzystywać znajomego, Bajteusz postanowił zużyć ich jak najmniej. Dodatkowo, w jednym z nich mogą znajdować się maksymalnie 2 eksponaty - przy większej ilości coś może się uszkodzić. Pomóż Bajteuszowi pisząc program, który obliczy minimalną ilość pudełek potrzebnych do spakowania wszystkich jego skarbów.

Wejście

W pierwszej linii wejścia znajduje się liczba testów t (t<1001). Każdy test składa się z kolei z dwóch wierszy: w pierwszym dwie liczby n i k (n≤106, k<1001) oznaczające odpowiednio ilość eksponatów w kolekcji Bajteusza oraz maksymalną pojemność pudełka. W drugim natomiast n liczb z przedziału 1..k, oznaczających wagi kolejnych przedmiotów.

Wyjście

Dla każdego testu jedna linia zawierająca minimalną ilość pudełek potrzebnych do spakowania całej kolekcji Bajteusza.

Przykład

Wejście:
1
7 20
4 10 18 6 16 20 13

Wyjście:
5

Dodane przez:Piotr Kąkol
Data dodania:2012-09-29
Limit czasu wykonania programu:0.300s-1.5s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: GOSU
Pochodzenie:ALGOLIGA
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.