==Include(page="template/taskheader" task_id="transport")==
 
==Include(page="template/raw")==
 
Transport
 
 
 
O firma ce produce saltele cu apa are N astfel de saltele intr-un depozit, asezate una peste alta (intr-o stiva). Fiecare saltea este caracterizata prin volumul sau (un numar intreg, exprimat in decimetri cubi). Pentru a le transporta la magazin, in vederea comercializarii, firma va inchiria un camion care va avea o capacitate egala cu C decimetri cubi. Acest camion va trebuie sa efectueze cel mult K transporturi (s-a estimat durata fiecarui transport si s-a ajuns la concluzia ca daca s-ar efectua mai mult de K transporturi, camionul ar ajunge la magazin in afara orelor de aprovizionare, astfel ca saltelele nu ar putea fi comercializate). La fiecare transport, camionul poate fi incarcat cu saltele, cu conditia ca suma volumelor saltelelor incarcate in camion sa nu depaseasca capacitatea camionului. Intrucat saltele sunt asezate intr-o stiva, nu este posibil sa se incarce in camion o saltea decat dupa ce au fost incarcate (si, eventual, transportate) toate saltelele de deasupra ei. Intrucat costul
inchirierii camionului depinde de capacitatea acestuia, firma doreste sa inchirieze un camion cu capacitatea cat mai mica care sa poata transporta toate cele N saltele, efectuand maxim K transporturi.
 
h2. Date de Intrare
 
Pe prima linie a fisierului transport.in se afla numerele intregi N si K (separate printr-un spatiu). Pe fiecare din urmatoarele N linii se afla un numar intreg, reprezentand volumul unei saltele. Prima din aceste N linii contine volumul saltelei din varful stivei, a doua linie contine volumul celei de-a doua saltele s.a.m.d.
 
h2. Date de Iesire
 
In fisierul transport.out veti afisa un singur numar intreg, reprezentand capacitatea minima pe care trebuie sa o aiba camionul pentru a putea transporta cele N saltele efectuand maxim K transporturi.
 
h2. Restrictii si precizari
 
. 1 <= N <= 16.000
 
. 1 <= K <= 16.000
 
. 1 <= volumul oricarei saltele <= 16.000
 
h2. Exemplu
 
transport.in transport.out Explicatie
6 3 8 La primul transport este incarcata prima saltea (care are volumul 7). La
cel de-al doilea transport sunt incarcate saltele 2 si 3 (volumul total
7 este 3 + 2 = 5). La cel de-al treilea transport sunt incarcate saltele
4, 5 si 6 (volumul total este 3 + 1 + 4 = 8).
3
 
2
 
3
 
1

==Include(page="template/taskheader" task_id="transport")==
 
O firma ce produce saltele cu apa are $N$ astfel de saltele intr-un depozit, asezate una peste alta (intr-o stiva). Fiecare saltea este caracterizata prin volumul sau (un numar intreg, exprimat in decimetri cubi). Pentru a le transporta la magazin, in vederea comercializarii, firma va inchiria un camion care va avea o capacitate egala cu $C$ decimetri cubi. Acest camion va trebuie sa efectueze cel mult $K$ transporturi (s-a estimat durata fiecarui transport si s-a ajuns la concluzia ca daca s-ar efectua mai mult de $K$ transporturi, camionul ar ajunge la magazin in afara orelor de aprovizionare, astfel ca saltelele nu ar putea fi comercializate). La fiecare transport, camionul poate fi incarcat cu saltele, cu conditia ca suma volumelor saltelelor incarcate in camion sa nu depaseasca capacitatea camionului. Deoarece saltele sunt asezate intr-o stiva, nu este posibil sa se incarce in camion o saltea decat dupa ce au fost incarcate (si eventual transportate) toate saltelele de deasupra ei. Intrucat costul inchirierii camionului depinde de capacitatea acestuia, firma doreste sa inchirieze un camion cu capacitatea cat mai mica care sa poata transporta toate cele $N$ saltele, efectuand maxim $K$ transporturi.
 
h2. Date de intrare
 
Pe prima linie a fisierului $transport.in$ se afla numerele intregi $N$ si $K$ (separate printr-un spatiu). Pe fiecare din urmatoarele $N$ linii se afla un numar intreg, reprezentand volumul unei saltele. Prima din aceste $N$ linii contine volumul saltelei din varful stivei, a doua linie contine volumul celei de-a doua saltele, etc.
 
h2. Date de iesire
 
In fisierul $transport.out$ veti afisa un singur numar intreg, reprezentand capacitatea minima pe care trebuie sa o aiba camionul pentru a putea transporta cele $N$ saltele efectuand maxim $K$ transporturi.
 
h2. Restrictii si precizari
 
* $1 ≤ N ≤ 16 000$
 
* $1 ≤ K ≤ 16 000$
 
* $1 ≤ volumul oricarei saltele ≤ 16 000$
 
h2. Exemplu
 
table(example). |_. transport.in|_. transport.out|
|6 3
7
3
2
3
1
4
|8|
 
_Explicatie_: la primul transport este incarcata prima saltea (care are volumul 7). La cel de-al doilea transport sunt incarcate saltele 2 si 3 (volumul total este 3 + 2 = 5). La cel de-al treilea transport sunt incarcate saltele 4, 5 si 6 (volumul total este 3 + 1 + 4 = 8).
 
 
==Include(page="template/taskfooter" task_id="transport")==

4
==Include(page="template/taskfooter" task_id="transport")==

506