Gigel are o bibliotecă cu T rafturi orizontale de diferite lungimi și T cutii cu cărți, câte o cutie pentru fiecare raft, în ordine. Cărţile dintr-o cutie au grosimi cunoscute și înălţimi egale cu înălţimea raftului pentru care sunt pregătite.

Gigel îşi doreşte foarte mult o bibliotecă nouă şi încearcă să o convingă pe mama sa folosind următoarea tactică: pe fiecare raft în parte el vrea să plaseze un număr minim de cărţi din cutia corespuzătoare astfel încât, așezându-le în anumite poziţii, să nu mai încapă nicio carte dintre cele rămase în acea cutie.

Cerința

Ajutați-l pe Gigel să determine, pentru fiecare raft, numărul minim de cărți ce pot fi alese din cutia corespunzătoare pentru a fi plasate pe raft în condițiile de mai sus.

Date de intrare

Fișierul de intrare carti.in conține pe prima linie numărul de rafturi T. Pe următoarele 2*T linii se găsesc informaţii despre rafturi și despre cărțile din cutiile corespunzătoare. Fiecare raft este descris pe două linii succesive: pe prima linie se află numerele N şi L separate printr-un singur spațiu, reprezentând numărul de cărți din cutie respectiv lungimea raftului. Pe a doua linie se află N numere naturale, separate printr-un singur spațiu, reprezentând grosimile celor N cărți din cutia corespunzătoare.

Date de ieșire

Fișierul de ieșire carti.out va conține T linii, câte una pentru fiecare raft. Pe fiecare linie va fi scris un singur număr ce reprezintă numărul minim de cărți plasate pe raftul respectiv în condițiile din enunț.

Restricții și precizări

• 1 ≤ T ≤ 13
• 1 ≤ L ≤ 10.000
• 1 ≤ N ≤ 100
• Gigel nu are nicio carte mai lată decât raftul pe care ar putea fi aşezată
• Distanţa dintre două cărţi consecutive plasate pe raft este un număr real pozitiv
• Orice carte aleasă se plasează în poziție verticală în întregime în interiorul raftului
• Modul de așezare pe raft este influențat doar de grosimea cărților
• Pentru 10% din teste N ≤ 13
• Pentru alte 15% din teste N ≤ 31 și L ≤ 100
• Pentru alte 35% din teste L ≤ 500

Exemplu:

carti.in

2 
5 23
1 4 4 4 1
2 13
5 4

carti.out

4
1

Explicație

Cărţi alese pentru raftul 1: 1, 1, 4 şi 4
Cărţi alese pentru raftul 2: 4