Problem U
Big 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 |
