B - Matboj

Časový limit: 5s, Pamäťový limit: 64MiB

Programovacie jazyky: Pascal, C, C++, Java, C++0x, Python 3

Počet bodov: 2

[ Pošli riešenie ] [ Tvoje riešenia ] [ Správne riešenia ] [ Vzorové riešenie ]

Na zajtrajší Košický matboj pripravujeme dvojčlenný tím. Ak by ste náhodou nevedeli, Matboj je matematická súťaž pozostávajúca z niekoľkých sérií.

Jedna séria obsahuje N úloh, na vyriešenie ktorých majú súťažiaci k dispozícii T minút. Kedže času je vždy málo, je dôležité si správne rozdeliť úlohy. Pred tým ako sa pustíme do riešenia danej série, spravíme preto mešiu analýzu. Ku každej úlohe Marián odhadne čas, ktorý by potreboval na jej vyriešenie. To isté urobí aj Janko. Potom si nejako rozdelia úlohy a každý z nich rieši samostatne.

Úloha

Aký najväčší počet úloh z danej série dokáže náš tím vyriešiť ?
Predpokladáme, že odhady časov sú presné a vieme ich vyrobiť zanedbateľne rýchlo.

Vstup

Prvý riadok vstupu obsahuje prirodzené číslo S určujúce počet sérii Matboja (1≤S≤50).
Ďalej bude nasledovať S popisov série v takomto tvare:

Prvý riadok obsahuje prirodzené čísla N T, 1≤N≤40, 1≤T≤80.
Druhý riadok obsahuje N čísel oddelených medzerou. i-te číslo zodpovedá času, ktorý potrebuje Marián na vyriešenie i-tej úlohy.
Tretí riadok obsahuje N čísel oddelených medzerou. i-te číslo zodpovedá času, ktorý potrebuje Janko na vyriešenie i-tej úlohy.

Všetky odhadované časy na vyriešenie úloh sú kladné celé čísla nie väčšie ako T.

Výstup

Pre každú sériu zo vstupu vypíšte najväčší počet úloh, ktoré dokáže náš tím vyriešit. Program má dokopy vypísať S čísel, každé v samostatnom riadku.

Príklad

Vstup

3
5 60
10 20 30 40 50
50 40 30 20 10
10 70
15 10 15 20 24 42 34 18 14 19
17 12 32 13 31 12 32 29 12 32
25 45
3 4 2 9 3 7 2 9 1 9 3 9 3 19 2 8 9 5 6 4 3 8 9 3 2
3 8 2 3 9 2 4 6 7 4 2 8 2 17 3 4 8 4 7 9 4 2 5 2 3

Výstup

5
8
24

02 Domáce 2