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.

-----Examples-----
Sample Input 1:
7 2
3 1 1 3 9 5 2
Sample Output 1:
16

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

见题面

见题面