Minimize Maximum Subarray Sum Partition

You are given an array of n positive integers and an integer K. Your task is to partition the array into exactly K contiguous subarrays such that the maximum sum among these subarrays is minimized. In other words, if the array is partitioned into subarrays with sums S₁, S₂, ..., S_K, you need to minimize the value of

$\max\{S_1, S_2, \ldots, S_K\}\$

This is a classical optimization problem that can be solved efficiently using binary search coupled with a greedy check.

inputFormat

The first line contains two integers n and K separated by a space, where 1 ≤ n ≤ 10⁵ and 1 ≤ K ≤ n.

The second line contains n positive integers representing the elements of the array.

outputFormat

Output a single integer, which is the minimized maximum sum among the K contiguous subarrays.

5 2
10 20 30 40 50

90