print2164. Пробка

printПробка

Ограничения: время – 2s/4s, память – 64MiB Ввод: input.txt или стандартный ввод Вывод: output.txt или стандартный вывод copy
Послать решение Blockly Посылки Темы Где Обсудить (0)

На односторонней дороге стоит светофор. Также, на этой дороге стоят `n` машин, которые хотят поскорее проехать. Однако, природная законопослушность мешает водителям ехать на красный и им приходится ждать зелёного, прежде чем ехать.
На светофоре есть только красный и зелёный цвета. Время, которым каждый свет горит, постоянно. Зелёный горит `g` секунд, затем красный горит `r` секунд, затем снова зелёный `g` секунд, и.т.д. В начальный момент светофор начинает светить зелёным. В момент переключения ехать можно.
На часах семь утра, все водители хотят спать, поэтому, они не сразу понимают, что уже можно ехать. А именно, для того, чтобы понять, что можно ехать, у `i`-го водителя уходит `a_i` секунд. То есть, он сможет поехать только через `a_i` секунд после того, как загорится зелёный, если он первый перед светофором, или после того как начнёт движение стоящий перед ним автомобиль, если в очереди он не первый. Автомобили ездят быстро, поэтому временем проезда светофора и временем подъезда к нему можно пренебречь. Несмотря на свою сонность, на красный свет водители реагируют мгновенно: ни один автомобиль не проедет на красный свет. Определите, через сколько секунд после первого включения зеленого свет уедет последний автомобиль.
В первой строке заданы целые числа `n` (`1\ ≤\ n\ ≤\ 1000`), `g` и `r` (`1\ ≤\ g,\ r\ ≤\ 10^9`) – Количество автомобилей, время зелёного и красного светов соответственно, в секундах. Далее, во второй строке задано `n` целых чисел `a_i` (`0\ ≤\ a_i\ ≤\ g`) – сколько секунд необходимо каждому водителю, чтобы осознать, что уже можно ехать.
Выведите единственное целое число – время, через которое уедет последний автомобиль.

Пример ввода

4 10 5
10 4 4 7

Пример вывода

37
В примере первый автомобиль проедет на 10-ой секунде, второй – на 19-ой секунде, третий – на 23-ей секунде и последний – на 37-ой.
Источник: neerc.ifmo.ru/school
loading