A river dock must ship n cargo units downstream using one barge. The units sit in a fixed loading queue and must be shipped in that exact order. Each day the barge loads the next contiguous run of still-waiting units (zero or more, but always taken from the front of the queue) whose total weight does not exceed the barge's per-day capacity, then sails.
You may choose any integer per-day capacity, but it stays the same every day. Find the smallest capacity that lets the dock finish shipping every unit within at most D days.
Input format
Line 1: two integers n and D.
Line 2: n space-separated integers, the cargo weights in queue order.
Output format
A single integer: the smallest per-day capacity that finishes within D days.
Constraints
- 1 <= D <= n <= 40
- 1 <= each weight <= 100000