O brutarie are n cuptoare care pot functiona in paralel. Cuptorul cu numarul i coace o tava de cozonaci in exact t_i minute; imediat ce o tava este gata, brutarul baga in cuptor urmatoarea, fara nicio pauza. Toate cuptoarele pornesc in acelasi moment (minutul 0), iar o tava se numara doar daca a fost coapta complet.
Pentru o comanda mare, brutaria are nevoie de cel putin M tavi de cozonaci. Determinati numarul minim de minute T dupa care cuptoarele, impreuna, au copt cel putin M tavi.
- Date de intrare
- Pe prima linie se afla numerele n si M. Pe a doua linie se afla n numere naturale nenule: t_1, t_2, ..., t_n (timpii de coacere ai cuptoarelor).
- Date de iesire
- Se afiseaza un singur numar natural: numarul minim de minute T.
- Restrictii
- 1 <= n <= 10 000 1 <= t_i <= 10 000 1 <= M <= 1 000 000 000
Exemple
Exemplul 1
Intrare
3 10 2 3 5
Iesire
10
Exemplul 2
Intrare
4 7 4 4 4 4
Iesire
8