A dock must ship n packages down a river using a single barge. The packages have positive integer weights and must be shipped in the given order. Each day the barge is loaded with a contiguous run of the next not-yet-shipped packages whose total weight does not exceed the barge's capacity C, then sails; the next day continues from where it left off.
Find the smallest capacity C such that all packages are shipped within at most D days. (C must be at least the heaviest single package, otherwise that package could never be loaded.)
Input format
Line 1: an integer n, the number of packages.
Line 2: n space-separated positive integers, the weights in shipping order.
Line 3: an integer D, the maximum number of days.
Output format
A single integer: the smallest feasible capacity C.
Constraints
- 1 <= n <= 100000
- 1 <= D <= n
- 1 <= each weight <= 1000000000