There are parcels on the conveyor belt that need to be delivered from one port to another within d days. The ship goes to another port once a day. i-th package on the conveyor belt has a weight of wi. The vessel takes on board the cargoes in the order in which they are located on the tape. Moreover, the ship will not be able to accommodate more parcels than its maximum carrying capacity.
You know the order in which the packages are placed on the conveyor belt. Find the minimum capacity of vessel that will be able to deliver all your packages to another port in d days.
Input
The first line of the input contains a natural number
N (N <= 5·10
4) - the number of parcels to be delivered. The second line contains
N numbers
wi. The
ith number means the weight of the
ith load on the conveyor belt (1 <= i <= N,1 <= w
i <= 500). Cargo with weight
w1 is loaded onto the vessel first. The third line contains the number
d (1 <= d <= 5·10
4)
Imprint
Print the minimum carrying capacity of a ship that can deliver all packages in
d days.
Explanation
In the first example, the ship's minimum carrying capacity is 15. Then the ship will be able to deliver our packages in 5 days as follows:
1st day: 1, 2, 3, 4, 5
2nd day: 6, 7
3rd day: 8
4th day: 9
5th day: 10
Please note that the cargo must be sent in the order indicated, so use a vessel with a capacity of 14 and separate the parcels into parts such as (2, 3, 4, 5), (1, 6, 7), (8), (9) , (10) is not allowed.
Examples
| # |
Input |
Output |
| 1 |
10
1 2 3 4 5 6 7 8 9 10
5 |
15 |
| 2 |
6
3 2 2 4 1 4
3 |
6 |
| 3 |
5
1 2 3 1 1
4 |
3 |