Дота 2
У популярній грі Dota 2 одним із наймиліших героїв, що може творити добро, є Crystal Maiden. Ця тендітна жінка спеціалізується на управлінні льодом і холодом. Зокрема, два найчастіше використовуваних нею скіли — це Frostbite (замороження одного ворога з обмеженням його руху та нанесенням шкоди) та Crystal Nova (уповільнення і нанесення шкоди всім ворогам у певній зоні).
У цій задачі вам потрібно допомогти ЦМочці знищити кілька нейтральних крипів, які вишикувались у ряд перед нею. При спробі знищити крипа, стріляючи по ньому з руки, вона виглядає настільки безпорадно, що її дійсно шкода... Тому вона використовує лише свої скіли 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 крипів.