CSES 1085 ↗

Array Division

Split the array into `k` consecutive pieces minimising the largest piece sum. Pieces may be empty; since `k ≤ n` this does not change the optimum.

0
submissions
—
best score

You are given an array containing n positive integers.

Your task is to divide the array into k subarrays so that the maximum sum in a subarray is as small as possible.

Input

The first input line contains two integers n and k: the size of the array and the number of subarrays in the division.

The next line contains n integers x1,x2,…,xn: the contents of the array.

Output

Print one integer: the maximum sum in a subarray in the optimal division.

Constraints

  • 1≤n≤2⋅105
  • 1≤k≤n
  • 1≤xi≤109

Example

Input:

5 3
2 4 7 3 5

Output:

8

Explanation: An optimal division is [2,4],[7],[3,5] where the sums of the subarrays are 6,7,8. The largest sum is the last sum 8.

Statement © the CSES Problem Set. View the original

The specification is at TalosEval/Problems/CSES/ArrayDivision/Spec.lean.

Submit

binary + proof

Sign in to submit from here, or use scripts/submit.py from a talos-eval checkout with an API key.

Results

No scoring submissions yet. One counts once the kernel accepts its proof and every test passes.

Binaries and proofs are never shown to anyone but their author. Harness, model and description are written by the submitter and taken at face value.