Minimum Maximum Group Sum Partition

You are given a sequence of n problems, each with a difficulty value. Your task is to divide these problems into m contiguous groups, such that the maximum sum of difficulties over all groups is minimized.

More formally, let \(a_1, a_2, \dots, a_n\) be the difficulties. You must partition this array into \(m\) contiguous subarrays. Define \(s_i\) to be the sum of difficulties in the \(i\)-th subarray. Your goal is to minimize \(X\), where

[ X = \max_{1 \le i \le m} s_i. ]

It is guaranteed that each problem must be assigned to some group, and the groups must cover all problems without reordering.

Hint: A common strategy to solve this problem is to use binary search on the potential answer space combined with a greedy check.

inputFormat

The input is given via standard input (stdin) in the following format:

1. The first line contains two space-separated integers \(n\) and \(m\), where \(n\) is the number of problems and \(m\) is the number of groups.
2. The second line contains \(n\) space-separated integers, where each integer represents the difficulty of a problem.

outputFormat

Output a single integer via standard output (stdout): the minimized possible value of the maximum group sum after partitioning the problems into m contiguous groups.

7 3
4 3 2 3 4 1 2

7