Ship Packages Within D Days

Packages with weights weights[0], weights[1], ... must be shipped in this order. Each day the ship carries a run of consecutive packages whose total weight is at most its capacity. Return the smallest capacity that ships all the packages within days days.

Examples

Example 1

Input:

ship_capacity([1, 2, 3, 4, 5, 6, 7, 8, 9, 10], 5)

Output:

15

Capacity 15 ships 1..5, 6 7, 8, 9, 10 in 5 days.

Example 2

Input:

ship_capacity([3, 2, 2, 4, 1, 4], 3)

Output:

6

Capacity 6 ships 3 2, 2 4, 1 4 in 3 days.

Constraints

• 1 <= len(weights) <= 2 * 10**4
• 1 <= days <= len(weights)
• 1 <= weights[i] <= 10**4
• Trying every capacity one by one is too slow for the large tests.