Дота 2
В популярной игре Дота 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 крипов.