Розбиття на k підмасивів
Розбиття на 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 підмасивів.
4 3 1 2 3 4
4
10 3 1 2 3 4 2 3 4 2 3 1
10