Minimize Maximum Daily Coding Time

Xiaohong has selected n programming problems numbered from \(1\) to \(n\) and plans to solve them in \(m\) days in order. Each problem \(i\) requires \(a_i\) time to solve. To help with her workload, she can ask her friend Xiaoming for help on at most one problem per day — the time for that problem is then waived. Thus, for any day with a set of problems \(S\), if the total time is \(\sum_{i \in S} a_i\) and the longest problem time is \(\max_{i \in S} a_i\), the effective time she spends that day is

[ \text{time} = \sum_{i \in S} a_i - \max_{i \in S} a_i, ]

Her goal is to partition the problems into \(m\) contiguous segments (one segment per day) so that the maximum daily time over all days, denoted as \(T\), is minimized. Compute the minimum possible \(T\).

inputFormat

The first line contains two integers \(n\) and \(m\) --- the number of problems and the number of days, respectively.

The second line contains \(n\) integers \(a_1, a_2, \dots, a_n\), where \(a_i\) represents the time required to solve the \(i\)-th problem.

outputFormat

Output a single integer: the minimum possible value of \(T\), which is the maximum daily coding time achieved under an optimal partition.

sample

5 2
3 1 4 1 5

4