A courier company has a line of parcels waiting to be delivered. The parcels must be sent in the order given. weights[i] is the weight of the i-th parcel.
One truck makes one trip every day. Each day you load parcels from the front of the line, one after another in order. The total weight on the truck can not go above the truck's capacity. All the parcels must be delivered within days days.
Return the smallest truck capacity that makes this possible.
You can not change the order of the parcels, and you can not skip a parcel to send a later one first.
Examples
Example 1:
Input: weights = [4,2,3,7,1,5], days = 3
Output: 9
Explanation: Capacity 9 works.
Day 1: 4, 2, 3 (total 9). Day 2: 7, 1 (total 8). Day 3: 5.
With capacity 8 you would need 4 days.
Example 2:
Input: weights = [5,5,5,5], days = 4
Output: 5
Explanation: Each day carries one parcel. The truck only needs to lift the heaviest parcel, which weighs 5.
Example 3:
Input: weights = [2,9,4,6], days = 2
Output: 11
Explanation: Day 1: 2 and 9 (total 11). Day 2: 4 and 6 (total 10). With capacity 10 you would need 3 days.