Code Submission Evaluation System | Login |

**Task** | Statistics

Time limit: | 1.00 s | Memory limit: | 512 MB |

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.

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 $x_1,x_2,\ldots,x_n$: the contents of the array.

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

- $1 \le n \le 2 \cdot 10^5$

- $1 \le k \le n$

- $1 \le x_i \le 10^9$

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$.