Managing Allowance

Hyunwoo wants to plan how to spend his allowance efficiently. For the next $N$ days, the amount of money he will spend each day is fixed, and he decides to withdraw money from his bank account exactly $M$ times.

Each time, Hyunwoo withdraws $K$ won from the account. He spends each day using the money he currently holds: if it is enough to cover that day's amount, he pays it and carries the rest over to the next day. If it is not enough, he first puts the leftover money back into the account, withdraws a fresh $K$ won, and then pays for that day.

Because Hyunwoo likes the number $M$, he wants the number of withdrawals to be exactly $M$. So even when he already has more than enough money for the day, he may choose to deposit the leftover back and withdraw $K$ won again. In other words, as long as the minimum number of withdrawals actually required is at most $M$, he can insert extra withdrawals to make the total exactly $M$.

To save money, Hyunwoo wants the withdrawal amount $K$ to be as small as possible. Write a program that finds the smallest $K$ that lets him get through all $N$ days while withdrawing exactly $M$ times.

The first line contains $N$ and $M$, separated by a space. ($1 \le N \le 100{,}000$, $1 \le M \le N$)

Each of the next $N$ lines contains the amount of money Hyunwoo will spend on the $i$-th day, one per line. ($1 \le \text{amount} \le 10{,}000$)

Print the minimum amount $K$ that Hyunwoo must withdraw from his account.