Розбиття на k підмасивів

Дано масив з $n$ елементів і число $k$. Розбийте даний масив на $k$ підмасивів (які мвстять в собі всі елементи). Обчисліть максимум серад сум елементів всіх $k$ підмасивів. Розбиття варто зробити так, щоб це значення було як можна меншим. Знайдіть цей максимум.

Вхідні дані

Перший рядок містить два числа $n$ і $k(n\le 10^6,1\le k\le n)$. Другий рядок містить $n$ натуральних чисел, кажне з яких не більше $10^9$.

Вихідні дані

Виведіть найменше можливе значення серед максимумів сум елементів всіх $k$ підмасивів.

Приклади

Для першого прикладу оптимальним разбиттям буде $\{1,2\},\{3\},\{4\}$. Максимум сум елементів серед всіх підмасивів дорівнює $4$, який є найменшим можливим для $3$ підмасивів.

Для другого прикладу оптимальним розбиттям буде $\{1,2,3,4\},\{2,3,4\},\{2,3,1\}$. Максимум сум елементів серед всіх підмасивів дорівнює $10$, який є найменшим можливим для $3$ підмасивів.