Олимпиадный тренинг

Задача . Доставка товаров


На конвейерной ленте расположены посылки, которые необходимо доставить из одного порта в другой в течение d дней. Судно отправляется в другой порт один раз в сутки. i-я упаковка на конвейерной ленте имеет вес wi. Судно принимает на борт грузы в том порядке, в котором они располагаются на ленте. Причем, судно не сможет вместить больше посылок, чем его максимальная грузоподъемность.

Вам известно, в каком порядке расположены посылки на конвейерной ленте. Найдите минимальную грузоподъемность судна, на котором вы сможете доставить все ваши посылки в другой порт за d дней.

 

Входные данные
Первая строка входных данных содержит натуральное число N (N <= 5·104) - количество посылок, которое необходимо доставить. Во второй строке записаны N чисел wi. i-е число означает вес i-го груза на конвейерной ленте (1 <= i <= N,1 <= wi <= 500). Груз с весом w1 погружается на судно первым.  В третьей строке записано число d (1 <= d <=  5·104)


Выходные данные
Выведите минимальную грузоподъемность судна, на котором можно доставить все посылки за 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



time 500 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w641
Python28
Комментарий учителя