Hide

# Problem ABig Boxes

Brandon Greg Jr. is moving to the United States to double his salary. He has $n$ items that he needs to pack into $k$ big boxes. The $n$ items are currently arranged in a row, and Brandon doesn’t want to bother reordering them, so he will partition the $n$ items into $k$ groups of consecutive items, and put each of the $k$ groups into their own box. For convenience when moving, Brandon wants to minimize the weight of the heaviest box. The weights of the boxes themselves are negligible.

## Input

The first line contains two space-separated integers $n$ and $k$ ($1\le k\le n\le 10^5$), denoting the number of items and the number of boxes respectively.

The second line of input contains $n$ space-separated integers $w_ i$ ($1\le w_ i\le 10^4$), representing the weight of each item in order.

## Output

The only line of output should contain a single integer, denoting the minimum possible weight of the heaviest box.

Sample Input 1 Sample Output 1
7 2
3 1 1 3 9 5 2

16

Sample Input 2 Sample Output 2
7 4
1 2 8 3 5 2 7

9

Sample Input 3 Sample Output 3
7 5
1 2 8 3 5 2 7

8

CPU Time limit 1 second
Memory limit 1024 MB
Statistics Show