Optimal Contiguous Grouping

Given n items arranged in a row with values \(a_1, a_2, \ldots, a_n\) and an integer \(k\), split the items into exactly \(k\) contiguous non-empty groups. For each grouping, compute the sum of values in each group, and let the cost of the grouping be the maximum of these sums. The goal is to minimize that maximum sum among all possible valid groupings.

Input Example: For example, if \(n = 5\), the items have values [6, 1, 3, 8, 4] and \(k = 2\), one valid grouping is:

• Group 1: \(6, 1, 3\) with sum 10
• Group 2: \(8, 4\) with sum 12

The cost for this grouping is \(\max(10, 12) = 12\), and it turns out this is the optimal solution.

Task: Given \(n\), \(k\) and the list of \(n\) integers, determine the minimum possible maximum group sum when the \(n\) items are partitioned into \(k\) contiguous groups.

inputFormat

The first line contains two integers \(n\) and \(k\), where \(1 \leq k \leq n\leq 10^5\). The second line contains \(n\) space-separated positive integers representing \(a_1, a_2, \ldots, a_n\) (\(1 \leq a_i \leq 10^9\)).

outputFormat

Output a single integer representing the minimal possible value of the maximum group sum when the items are divided into exactly \(k\) contiguous groups.

sample

5 2
6 1 3 8 4

12