На конвейерной ленте расположены посылки, которые необходимо доставить из одного порта в другой в течение d дней. Судно отправляется в другой порт один раз в сутки. i-я упаковка на конвейерной ленте имеет вес wi. Судно принимает на борт грузы в том порядке, в котором они располагаются на ленте. Причем, судно не сможет вместить больше посылок, чем его максимальная грузоподъемность.
Вам известно, в каком порядке расположены посылки на конвейерной ленте. Найдите минимальную грузоподъемность судна, на котором вы сможете доставить все ваши посылки в другой порт за d дней.
Входные данные
Первая строка входных данных содержит натуральное число
N (N <= 5·10
4) - количество посылок, которое необходимо доставить. Во второй строке записаны
N чисел
wi.
i-е число означает вес
i-го груза на конвейерной ленте (1 <= i <= N,1 <= w
i <= 500). Груз с весом
w1 погружается на судно первым. В третьей строке записано число
d (1 <= d <= 5·10
4)
Выходные данные
Выведите минимальную грузоподъемность судна, на котором можно доставить все посылки за
d дней.
Пояснение
В первом примере минимальная грузоподъемность судна равна 15. Тогда судно сможет доставить наши посылки в 5 дней следующим образом:
1-й день: 1, 2, 3, 4, 5
2-й день: 6, 7
3-й день: 8
4-й день: 9
5-й день: 10
Обратите внимание, что груз должен быть отправлен в указанном порядке, поэтому использовать судно грузоподъемностью 14 и разделить посылки на части, такие как (2, 3, 4, 5), (1, 6, 7), (8), (9), (10) не допускается.
Примеры
| № |
Входные данные |
Выходные данные |
| 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 |