Misiunea unui robot este de a lua obiecte de pe o bandă de asamblare, în ordinea în care acestea vin pe bandă şi de a le introduce în containere identice de capacitate gmax.
La fiecare moment de timp numai două containere sunt disponibile. După ce ia un obiect de pe bandă, robotul poate alege între:
– a plasa obiectul în unul dintre cele două containere disponibile, dacă este posibil (adică dacă nu se depăşeşte capacitatea maximă gmax);
– a închide unul dintre cele două containere şi a deschide unul nou, pentru a pune în el obiectul.
Atenţie! După ce a fost închis un container, acesta este sigilat şi nu poate fi redeschis.

Cerinţă

Scrieţi un program care să determine numărul minim de containere necesar pentru a transporta obiectele de pe banda de asamblare dacă se cunoaşte n numărul de obiecte, greutăţile obiectelor gi (i =1, …, n) precum şi capacitatea gmax a unui container.

Date de intrare

Fişierul de intrare banda1.in conţine
n gmax – numărul de obiecte şi capacitatea unui container
g1 g2 … gn – greutăţile celor n obiecte

Date de ieşire

Fişierul de ieşire banda1.out conţine pe prima linie:
k – numărul minim de containere necesare transportului

Restricţii

n ≤ 25
0 < gmax ≤ 100
0 < gi ≤ 100

Exemple

banda1.in	banda1.out
6 8 4 2 5 3 5 4	3

autor: Prof. Lucia Miron

propunător: Prof. Marinel Şerban

Liceul de Informatică “Grigore Moisil”

marinel_serban@yahoo.com