Rezolvare PBinfo #4009

Cerința

Moș Crăciun pregătește cadourile pentru acest an. El cunoaște prețurile a n cadouri și are la dispoziție o sumă de bani S. Ajutați-l să aleagă un număr maxim de cadouri a căror preț total să nu depășească S și determinați suma minimă de care mai are nevoie Moș Crăciun pentru a cumpăra încă un cadou.

Date de intrare

Programul citește de la tastatură numerele n S, iar apoi n numere naturale, reprezentând prețurile cadourilor.

Date de ieșire

Programul va afișa pe ecran două numere, k p, separate printr-un spațiu, reprezentând numărul maxim de cadouri pe care le poate cumpăra Moș Crăciun și suma minimă de care mai are nevoie pentru a cumpăra încă un cadou.

Restricții și precizări

• 1 ≤ n ≤ 1000
• 1 ≤ S ≤ 1 000 000 000
• prețurile cadourilor vor fi mai mici decât 1 000 000
• Luca spune că dacă Moșul poate cumpăra toate cele n cadouri, nu mai plătește nimic pentru alt cadou!!!

Exemplu:

Intrare

5 10
7 2 6 4 3

Ieșire

3 5

Explicație

Cu suma dată Moș Crăciun va cumpăra trei cadouri, cele cu prețurile 2 4 3. Mai are nevoie de încă 5 (bani) ppentru a putea cumăra și cadoul cu prețul 6.