Capacity to Ship Packages Within D Days

There are n packages that needs to be transported from one city to another, and you need to transport them there within d days. For the ith package, the weight of the package is weights[i]. You are required to deliver them in order, and in order to minimize the cost, you want to deliver the packages in one truck once per day, with a capacity as small as possible to save truck rental cost. What is the minimum capacity of the truck that is required to deliver all packages within d days?

Input

• weights: A list of packages and their weights.
• d: The number of days to deliver all packages.

Output

The minimum capacity of the truck.

Examples

Example 1:

Input:

weights = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
d = 5

Output: 15

Explanation:

The 1st day we deliver the first 5 package. The 2nd day we deliver the next 2, and for each following days, we deliver 1. The maximum weight delivered on each day is 15, so we can have a truck with a capacity of 15. This value is the minimum.

Constraints

• 1 <= len(weights) <= 5 * 10^4
• 1 <= d <= len(weights)
• 1 <= weights[i] <= 500

Try it yourself

Solution