Fajomonth Budget Minimization

Farmer John, an exceptional accounting wizard, has predicted his farm will soon run out of money and needs to budget his upcoming expenses. He has determined exactly how much money he will spend each day over the next \(N\) days where \(1 \leq N \leq 100000\) and the daily expense \(money_i\) satisfies \(1 \leq money_i \leq 10000\). 

John wants to split these \(N\) consecutive days into exactly \(M\) "fajomonths" (\(1 \leq M \leq N\)). Each fajomonth is a contiguous block of one or more days, and every day must belong to exactly one fajomonth.

The goal is to arrange the fajomonths so that the maximum total spending of any fajomonth is minimized. In other words, if the total spending for each fajomonth is computed, John wants the largest of these totals to be as small as possible.

Input/Output Example:

For example, if \(N=7\), \(M=5\) and the expenses over 7 days are:

(100\ 400\ 300\ 100\ 500\ 101\ 400)

One possible partition is: [100,400], [300,100], [500], [101], [400] with fajomonth sums: 500, 400, 500, 101, 400. The maximum sum is 500 and it turns out to be optimal.

inputFormat

The first line of input contains two space-separated integers \(N\) and \(M\), representing the number of days and the number of fajomonths respectively.

The second line contains \(N\) space-separated integers, where the \(i^{th}\) integer \(money_i\) indicates the spending on day \(i\).

outputFormat

Output a single integer: the minimum possible value of the maximum fajomonth spending when the days are partitioned optimally.

sample

7 5
100 400 300 100 500 101 400

500