Minimize Maximum Partition Sum

You are given an array of N positive integers, representing the costs, 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.

Formally, if the array is partitioned into subarrays S₁, S₂, ..., S_K, you want to minimize the value:

[ \min; \max_{1 \le i \le K} \left{\sum_{j \in S_i} C_j\right} ]

Note: It is guaranteed that a valid partition exists. All input numbers are positive. The subarrays must be contiguous.

inputFormat

The first line contains a single integer N (the number of elements in the array).

The second line contains N space-separated positive integers, representing the array C.

The third line contains a single integer K (the number of subarrays to partition the array into).

outputFormat

Output a single integer, the minimized maximum sum among the K subarrays after partitioning.

5
1 2 3 4 5
3

6