Un vapor trebuie sa transporte n colete, in ordinea data, in cel mult D zile. In fiecare zi, coletele se incarca in ordine (fara a le reordona), fara ca suma greutatilor incarcate intr-o zi sa depaseasca o capacitate fixata a vaporului; fiecare zi in care se transporta ceva trebuie sa contina cel putin un colet. Determinati capacitatea minima a vaporului astfel incat toate cele n colete sa poata fi transportate in cel mult D zile.
- Date de intrare
- Pe prima linie se afla numerele naturale n si D, separate printr-un spatiu. Pe a doua linie se afla cele n numere naturale reprezentand greutatile coletelor, in ordinea in care trebuie incarcate.
- Date de iesire
- Afiseaza pe o singura linie capacitatea minima ceruta.
- Restrictii
- 1 <= D <= n <= 25000, 1 <= greutate <= 10^4
Exemple
Exemplul 1
Intrare
10 5 1 2 3 4 5 6 7 8 9 10
Iesire
15
Exemplul 2
Intrare
6 3 3 2 2 4 1 4
Iesire
6