farfurii

In bucataria unei gospodine se afla un teanc format din N farfurii. Gospodina care urmeaza sa le spele este pusa in fata unei probleme. Ea cunoaste cat timp dureaza spalarea fiecarei farfurii. De asemenea ea poate sa renunte la spalarea ei si sa o sparga, insa spargerea dureaza exact un minut, pentru oricare farfurie. Farfuriile sunt numerotate cu numere de la 1 la N, incepand cu farfuria din varful teancului spre cea de la baza teancului. Farfuria care poate fi spalata la un moment dat este cea situata in varful teancului. Initial gospodina poate spala sau sparge farfuria cu numarul 1, dupa care poate face acelasi lucru cu farfuria numarul 2, s.a.m.d. De asemenea, gospodina poate lasa in teanc farfurii nespalate.
Este cunoscut timpul T exprimat in minute, pe care gospodina il are la dispozitie.

Cerinta

Realizati un program care determina care este numarul maxim de farfurii pe care le poate spala gospodina in timpul T dat. Pentru acest numar maxim de farfurii obtinut, determinati si timpul minim necesar spalarii lor.

Date de intrare

Fisierul de intrare farfurii.in contine pe prima linie doua numere naturale N T separate printr-un spatiu, reprezentand numarul de farfurii si respectiv timpul avut la dispozitie de gospodina. Pe urmatoarea linie se gaseste un sir de N numere naturale ts1, ts2, ..., tsN, separate prin cate un spatiu, reprezentand timpii de spalare al fiecarei farfurii, in ordine, incepand cu farfuria 1.

Date de iesire

In fisierul de iesire farfurii.out se vor scrie pe o singura linie numerele Nmax si Tmin despartite printr-un spatiu. Nmax reprezinta numarul maxim de farfurii pe are le poate spala gospodina in timpul T, iar Tmin timpul minim de spalarea lor.

Restrictii

0 < N <= 1000
0 < T <= 10000
0 <= tsi<= 100

Exemplu

farfurii.in farfurii.out farfurii.in farfurii.out Explicatii
4 4
1 4 1 3 		2 3
 7 11
10 3 2 1 4 2 4 		4 10 Primul exemplu:
Se spala prima farfurie (1 min), se sparge a doua farfurie (1 min), se spala a treia farfurie (1 min).

Al doilea exemplu:
Se sparg farfuriile 1 si 5 si se spala farfuriile 2, 3, 4 si 6.
(Tmin=1+3+2+1+1+2=10)

Timp maxim de executie/test: 0.5 secunde

prof. Dana Lica
Colegiul National “Ion Luca Caragiale” Ploiesti
Contact: danal182001@yahoo.com