Minimize Maximum Subarray Sum Partitioning

You are given an array (A) of (n) integers and a positive integer (k). Your task is to partition the array into exactly (k) non-empty contiguous subarrays such that the maximum sum over these subarrays is minimized. In other words, if you denote the sum of elements in each partition as (S_1, S_2, \dots, S_k), you need to minimize (\max(S_1, S_2, \dots, S_k)).

For example, consider (A = [7, 2, 5, 10, 8]) and (k = 2). One optimal partition is ([7,2,5]) and ([10,8]) with subarray sums (14) and (18), so the answer is (18).

inputFormat

The input is given via standard input (stdin) and consists of two lines.

The first line contains two integers (n) and (k) ((1 \leq k \leq n \leq 10^5)), where (n) is the number of elements in the array and (k) is the number of partitions.

The second line contains (n) space-separated integers representing the array (A).

outputFormat

Output a single integer, which is the minimized maximum sum among the (k) contiguous subarrays.## sample

5 2
7 2 5 10 8

18