Capacity to Ship Packages

Problem statement

A ferry loads packages in their arrival order and makes at most one shipment per day. Every shipment uses the same weight capacity. The operator must choose the smallest capacity that clears the waiting packages within the allowed number of days. Your task Find the minimum ship capacity that transports all packages within days days. Each day loads a contiguous next portion of the sequence without exceeding capacity. Important details Packages cannot be split or reordered. A capacity must fit the heaviest individual package. Finishing earlier than the deadline is allowed. Search the capacity range using the monotonic relationship between capacity and required days. Worked example For weights [3, 2, 4, 1] and two days, capacity 5 ships [3, 2] then [4, 1]. Capacity 4 needs three days, so the answer is 5.

Input format

First line: n days. Next line: n weights.

Output format

Print the smallest capacity.

Constraints

1 <= days <= n <= 50000; 1 <= weights <= 500.

Sample input

4 2
3 2 4 1

Sample output

5