Дано масив з елементів і число . Розбийте даний масив на підмасивів (які мвстять в собі всі елементи). Обчисліть максимум серад сум елементів всіх підмасивів. Розбиття варто зробити так, щоб це значення було як можна меншим. Знайдіть цей максимум.
Перший рядок містить два числа і . Другий рядок містить натуральних чисел, кажне з яких не більше .
Виведіть найменше можливе значення серед максимумів сум елементів всіх підмасивів.
Для першого прикладу оптимальним разбиттям буде . Максимум сум елементів серед всіх підмасивів дорівнює , який є найменшим можливим для підмасивів.
Для другого прикладу оптимальним розбиттям буде . Максимум сум елементів серед всіх підмасивів дорівнює , який є найменшим можливим для підмасивів.