Максим вырос, разочаровался в большой науке и теперь работает авиадиспетчером. Каждый день он делает очень важное и ответственное дело: сажает самолеты.
Этот процесс не такой уж сложный, как может показаться на первый взгляд. В аэропорту, в котором работает Максим, всего одна посадочная полоса, поэтому самолеты должны садиться по очереди. Посадка занимает b минут. Если самолет прилетел, а посадочная полоса занята, его отправляют совершать дополнительные круги над городом до тех пор, пока он не прилетит к аэропорту со свободной взлётно-посадочной полосой. Один круг занимает f минут. Если посадочная полоса свободна, самолёт немедленно начинает посадку. Если несколько самолётов подлетают к аэропорту со свободной посадочной полосой одновременно, то один из них идёт на посадку, а другие отправляются совершать дополнительные круги.
Сегодня в аэропорт должны прилететь n самолетов, известно время прилета каждого из них. За какое время все самолёты совершат посадку?
Входные данные
В первой строке даны три целых числа n, b, f — количество самолетов (1≤n≤1000), время, которое занимает посадка и время, которое занимает один круг над аэропортом (1≤b, f≤10
9 ). В следующей строке дано n целых чисел t
i — времена прибытия самолетов, перечисленные в произвольном порядке (0≤t
i≤10
9 ).
Выходные данные
Выведите одно число: время, за которое все самолёты совершат посадку.
Примеры
| № |
Входные данные |
Выходные данные |
| 1 |
10 5 12
13 0 1 10 20 20 2 1 10 20 |
79 |