A conveyor belt has packages with weights. You need to ship all packages within D days. Packages must be shipped in order. Return the minimum weight capacity of the ship.

Example 1:

Input weights: 1 2 3 4 5 6 7 8 9 10
days: 5
Output: 15

Example 2:

Input weights: 3 2 2 4 1 4
days: 3
Output: 6

Constraints:

• 1 ≤ D ≤ weights.length ≤ 500
• 1 ≤ weights[i] ≤ 500

Input format: First line: space-separated weights. Second line: D.

Output format: Minimum ship capacity.