Warehouse Capacity

Packages sit on a conveyor in a fixed order and must be shipped in that order within D days. Each day, one truck is loaded with a contiguous run of the remaining packages; the total weight loaded in a day cannot exceed the truck's capacity.

Find the minimum truck capacity that allows shipping all packages within D days.

Input

The first line contains two integers n and D — the number of packages and the number of days.

The second line contains n integers w₁ … wₙ — the package weights in conveyor order.

Output

Print the minimum capacity.

Constraints

• 1 ≤ D ≤ n ≤ 2·10⁴
• 1 ≤ wᵢ ≤ 10⁷

5 3
3 2 2 4 1

5

3 1
1 2 3

6