Description

Farmer John is a meticulous accountant. He realizes that he might not have enough funds to keep his farm running.
He has calculated and recorded the daily expenses required for the next N (1 ≤ N ≤ 100,000) days. John plans to create budgets for M (1 ≤ M ≤ N) consecutive fiscal periods, which he calls fajo months. Each fajo month consists of one or more consecutive days, and every day must be included in exactly one fajo month.

John's goal is to arrange the number of days in each fajo month such that the maximum monthly expense among all fajo months is as small as possible.

Input Format

The first line contains two integers, N and M, separated by a single space.
The next N lines each contain an integer between 1 and 10,000, representing the daily expenses for the next N days in order.

Output Format

An integer representing the smallest possible value of the maximum monthly expense.

7 5
100
400
300
100
500
101
400

500

Hint

If John combines the first two days as one month, the third and fourth days as another month, and the last three days as a third month, the maximum monthly expense will be 500. Any other allocation scheme would result in a larger value.