Laiko ribojimas: 1s

Atminties ribojimas: 64MB

Jei norite pateikti savo sprendimą - prisijunkite.

Sekos suskaldymas

Duota n skaičių seka a_1,a_2,...,a_n, kurią norima padalinti į k dalių. Kiekvienas skaičius turi patekti į lygiai vieną kažkurią iš šių k dalių, o visi skaičiai, patenkantys į tą pačią dalį, sekoje turi eiti vienas po kito.

Be to, norima seką padalinti taip, kad didžiausia suma tarp visų dalių būtų kuo mažesnė. Tai reiškia, kad kiekvienai daliai randame sumą skaičių, kurie patenka į ją, ir paimama didžiausia tokia suma tarp visų dalių - jūsų tikslas taip padalinti seką, kad didžiausia suma tarp visų dalių būtų mažiausia įmanoma.

Raskite šią sumą.

Pradiniai duomenys

Pirmoje eilutėje duoti du natūralieji skaičiai n ir k (1\\leqk\\leqn\\leq2\\cdot10^5) - sekos narių kiekis ir skaičius dalių, į kiek norėtų padalinti pradinę seką.

Antroje eilutėje pateikta n natūraliųjų skaičių a_1,a_2,...,a_n (1\\leqa_i\\leq10^9) - sekos nariai.

Rezultatai

Išveskite vieną skaičių - didžiausią įmanomą sumą.

Pavyzdys

Duomenys Rezultatai 
5 3
2 4 7 3 5
 
8

Paaiškinimas

Duota seka [2,4,7,3,5]. Optimalus jos padalinimas į tris dalis atrodytų taip: [2,4],[7],[3,5] - šių trijų dalių sumos yra 6,7,8; didžiausia iš jų yra 8. Kadangi neįmanoma padalinti sekos į tris dalis taip, kad didžiausia suma būtų mažesnė už 8, tai šis skaičius ir yra atsakymas.