Вам надано масив, що містить ~n~ додатних цілих чисел.

Ваше завдання — розділити масив на ~k~ підмасивів так, щоб максимальна сума в підмасивах була якомога меншою.

Обмеження

• ~1≤n≤2⋅10^5~
• ~1≤k≤n~
• ~1≤x_i ​ ≤10^9~

Формат вхідних даних

Перший рядок містить два цілі числа ~n~ і ~k~: розмір масиву та кількість підмасивів у поділі.

Наступний рядок містить ~n~ цілих чисел ~x_1 ​ , x_2 ​ ,…, x_n~ ​ : вміст масиву.

Формат вихідних даних

Вивести одне ціле число: максимальну суму в підмасиві в оптимальному діленні.

Приклад вхідних даних

5 3
2 4 7 3 5

Приклад вихідних даних

8

Пояснення:

Оптимальним є поділ [2,4],[7],[3,5] де суми підмасивів 6,7,8. Найбільша сума — остання сума 8.