481. Capacity to Ship Packages Within D Days

Given the weights of packages that must be shipped in their given order, and D days, return the least ship capacity so that all packages are shipped within D days. Each day you load consecutive packages without exceeding the capacity. Input: '[weights], D'.

Input: '[weights], D'.

Output: Integer — the minimum capacity.

Examples

Input: [1,2,3,4,5,6,7,8,9,10], 5
Output: 15
Explanation: Capacity 15 ships in 5 days.

Input: [3,2,2,4,1,4], 3
Output: 6
Explanation: Minimum feasible capacity.

Input: [1], 1
Output: 1
Explanation: One package, one day.

Constraints

• 1<=D<=n<=5*10^4
• 1<=weight<=500

Asked by