0056. OH!

Input file name:	input.txt
Output file name:	output.txt
Time limit:	1 s
Memory limit:	64 megabytes

На первом этаже Всемирного торгового центра в момент атаки самолёта, управляемого исламским фундаменталистом Запоем Маглоевым, находится Чапаев, который мечтает лишить здание спиртного, пока сотрудники спускаются по внешним пожарным лестницам. Он может передвигаться на лифте, который двигается со скоростью K этажей в минуту. Пожар распространяется со скоростью L этажей в минуту, но не быстрее лифта. На то, чтобы выпить весь спирт на этаже, Василию Ивановичу надо M минут (вне зависимости от количества спирта). Если лифт проезжает через горящий этаж, или пожар приходит на тот этаж, на котором находится лифт √ лифт застревает и Василий Иванович вынужден избавиться от всего выпитого естественным путём. Василию Ивановичу заранее известно, сколько спирта на каждом этаже, а также номер нижнего этажа, охваченного пожаром √ P. Определите максимальное число выпитого Василием Ивановичем спирта.

Формат входного файла

В первой строке записаны натуральные числа P,K,L,M ≤ 1024, N ≤ 100000, P ≤ 512. В последующих N-1 строках содержатся числа √ количество бутылок спирта на каждом этаже, начиная со второго до последнего. Спирта на этаже не более 65536.

Формат выходного файла

В выходном файле должно быть число √ максимальное количество спирта, которое выпьет Василий Иванович.

Пример:

input.txt	output.txt
5 1 1 1 5 100 100 100 100	100

Clarification1: Если огонь приходит на этаж в тот момент, когда лифт уезжает, лифт застревает. Лифт должен иметь запас времени по сравнению с огнем.

Clarification2: Василий Иванович всегда допивает весь спирт на этаже до конца!

Source: Petrozavodsk training camp, Summer 2002. Magloy's contest :-)
Author: Magloy (Alexander Korol, Denis Vlasov, Roman Soshkin)

Discuss       Submit a solution



Printable version