eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Дота 2

Дота 2

Ліміт часу 2 секунди
Ліміт використання пам'яті 256 MiB

В популярной игре Дота 2, одним из самых няшных героев, за которых можно творить добро, является Crystal Maiden. Это маленькая хрупкая женщина специализируется на управлении льдом и холодом. В частности, два самых частых используемых ею скилла – это Frostbite (заморозка одного врага с запрещением передвижения и нанесением урона) и CrystalNova (замедление и нанесение урона всем врагам в некоторой площади).

В данной задаче Вам необходимо помочь ЦМочке уничтожить несколько нейтральных крипов, выстроившихся в ряд перед ней. При попытке уничтожить крипа, стреляя по нему с руки, она выглядит настолько беспомощно, что ее действительно жалко... Поэтому она использует только свои скиллы Frostbite и Crystal Nova. При использовании Frostbite первый живой крип в ряду получает FD урона, но при этом тратится FM маны. При использовании Crystal Nova первый живой крип в ряду, а так же следующий за ним крип (если он жив) получают по CD урона, но при этом тратится CM маны. Если следующий крип уже мертв (например, в результате действия предыдущих Crystal Nova) или крип остался вовсе один, то урон наносится только первому крипу. Изначально у Crystal Maiden имеется запас в Mманы и перед ней стоит N крипов. Определите, какое наибольшее число крипов может убить ЦМочка. Ice take you!

Вхідні дані

В первой строке входного файла содержатся два целых числа – количество крипов N (1 ≤ N ≤ 300) и запас маныCrystal Maiden – M (1 ≤ M ≤ 300). Во второй строке содержатся 4 целых числа FD, FM, CD, CM (1 ≤ FD, FM, CD, CM ≤ 300). В следующей строке находятся N целых чисел H_i – количество единиц жизни у крипов в том порядке, в котором они стоят перед Crystal Maiden (1 ≤ H_i ≤ 300). Если после применения скилла ЦМкой у крипа становится неположительное число единиц жизни, то считается, что крип умирает и герой может атаковать следующего крипа.

Вихідні дані

Вывести единственное число — наибольшее возможное количество убитых Crystal Maiden крипов.

Приклад

Вхідні дані #1
2 2
1 1 1 1
2 1
Вихідні дані #1
2
Автор Алексей Шмелев
Джерело Osipovsky Cup - 2013