Minimizing Maximum Subarray Sum

Given an array of integers and an integer $$k$$, partition the array into $$k$$ contiguous subarrays such that the maximum subarray sum is minimized. Formally, if the subarray sums are denoted by $$S_1, S_2, \dots, S_k$$, the goal is to minimize $$\max_{1 \le i \le k} S_i$$.

Your program should read input from standard input (stdin) and write the result to standard output (stdout).

inputFormat

The first line contains two integers $$n$$ and $$k$$ where $$n$$ is the number of elements in the array and $$k$$ is the number of subarrays to partition.

The second line contains $$n$$ space-separated integers representing the array elements.

outputFormat

Output a single integer, which is the minimized maximum subarray sum after partitioning the array into $$k$$ subarrays.

5 3
1 2 3 4 5

6