eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

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

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

Ліміт часу 1 секунда
Ліміт використання пам'яті 128 MiB

Дано масив з 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 підмасивів.

Вхідні дані #1
4 3
1 2 3 4
Вихідні дані #1
4
Вхідні дані #2
10 3
1 2 3 4 2 3 4 2 3 1
Вихідні дані #2
10