# Problem H

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 |