eolymp
Competitions

Жадібні алгоритми

Гонки

Time limit 1 second
Memory limit 32 MiB

Велосипедист готовится к горным велогонкам с раздельным стартом (то есть н время). Он оценил свою ожидаемую скорость использования энергии (то есть мощность) в зависимости от времени после начала гонки и хочет разработать соответствующий график питания на протяжении гонок. Единственным источником энергии велосипедиста будут углеводы в питательных батончиках. Все батончики одинаковы и содержат два типа углеводов: быстро усваиваемые (моно- и дисахариды) и медленно усваиваемые (полисахариды). Эффект от потребления одного батончика можно приблизить такой моделью: первые t1 секунд после потребления батончик позволяет велосипедисту развить мощность a милливатт ("быстрые" углеводы), следующие t2 секунд - мощность b милливатт ("медленные" углеводы). После этого эффект от потребления батончика полностью пропадает. Для упрощения будем считать:

  • модель пищеварения и использования углеводов линейная, то есть мощности от потребления разных батончиков в произвольный момент времени складываются;

  • излишки энергии не накапливаются;

  • велосипедист может потреблять батончики мгновенно когда угодно во время или до начала гонок.

Найти наименьшее количество батончиков, необходимых для удовлетворения энергетических потребностей велосипедиста на все время гонок.

Input data

Первая строка содержит пять целых чисел n, t1, t2, a, b - ожидаемое время гонок в секундах и параметры батончика, 1n, t1, t2105, 1a, b109.

Вторая строка содержит n целых чисел p0, p1, ..., pn–1 - величины желаемой мощности велосипедиста для каждой секунды после начала гонок, 1pj109.

Output data

Вывести единственное число - минимальное необходимое количество батончиков.

Examples

Input example #1
7 2 3 5 2
3 4 5 5 5 4 5
Output example #1
4
Author Дмитро Кордубан
Source ІІІ (городской) этап Всеукраинской олимпиады школьников по информатике, 2014, г. Киев