Antonio a primit de ziua lui multe DVD-uri cu jocuri pentru noul său PSP (PlayStation Portable, consolă de jocuri) şi le-a asezat pe masă în ordinea în care s-a hotărât să le instaleze.
Spaţiul de memorie disponibil pe PSP este de S megabytes, iar spaţiul de memorie necesar fiecărui joc (exprimat în megabytes) este scris pe carcasa DVD-ului jocului.
Antonio ar vrea să aibă instalate cât mai multe jocuri noi. Nefiind un tip foarte isteţ, Antonio decide să analizeze în ordine jocurile: dacă jocul încape în spaţiul disponibil, îl va instala, dacă nu – va trece la următorul.
Cerinţă
Ştiind spaţiul de memorie disponibil pe PSP-ul lui Antonio, numărul de jocuri primite şi dimensiunea în megabytes a fiecărui joc în ordinea în care a decis să le instaleze, să se determine numărul maxim de jocuri pe care le va instala şi spaţiul de memorie liber rămas pe PSP după instalare.
Date de intrare
Din fişierul psp.in se citesc, din prima linie, separate prin spaţiu, N numărul de jocuri primite şi S dimensiunea spaţiului de memorie liber pe PSP. De pe a doua linie se citesc, separate prin spaţiu, cele N numere naturale nenule a1 a2 ... aN reprezentând dimensiunile fiecărui joc, în ordinea în care Antonio s-a hotărât să le instaleze.
Date de ieşire
În fişierul psp.out se vor scrie prima linie, separate prin spaţiu, numărul maxim de jocuri instalate apoi spaţiul de memorie liber rămas pe PSP după instalarea lor.
Restricţii
• 1 ≤ N ≤ 500
• 0 < S ≤ 30000
• 0 < ai ≤ 1000 , i=1, 2, … N
Exemple
psp.in
psp.out
Explicaţii
6 100
20 45 75 25 20 15
3 10
Respectând ordinea în care le-a aşezat pe masă, Antonio reuşeşte să instaleze doar 3 jocuri (primul, al doilea şi al patrulea). Spaţiul liber rămas va fi 10 megabytes din cei 100 iniţiali pentru că cele trei jocuri ocupă în total 90 megabytes (20+45+25).