Вам надано масив, що містить \(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.