Zota 2
In a popular game Zota 2, one of most nice heroes is "Crystal Maiden". She is a girl, specialized on controlling Ice and Cold. Particularly, two of her skills are - "Frostbite" (freezes one enemy, denies movement, and causes damage) and "Crystal Nova" (slows and damages all enemies at some area).
You are to help the hero to use her skills properly and defeat neutral creeps, standing in front of her in a row.
When she uses Frostbite, closest alive creep gets FD points of damage, but Crystal Maiden spends FM points of mana.
When she uses Crystal Nova, closest alive creep and the next creep after him (if alive) get CD points of damage each, but CM points of mana are spent. If that next creep is already dead (for example, due to early Crystal Nova hits), or the closest alive creep is the last one, then only the closest alive creep is damaged.
Initially Crystal Maiden has M points of mana and there are N creeps in front of her. You are to define, how many creeps the hero can defeat.
Input
First line of input contains two integer numbers - the quantity of creeps N (1 ≤ N ≤ 300) and initial hero mana M (1 ≤ M ≤ 300). Next line contains 4 integer numbers: FD, FM, CD, CM (1 ≤ FD, FM, CD, CM ≤ 300). Next line contains N integer numbers Hi, separated by spaces - the quantity of health points of the corresponding creep. The order of numbers H_i is the order of the creeps in row. If after Crystal Maiden's spellcast, a creep has non-positive quantity of remaining health points, the creep dies, and the hero can attack the next creep.
Output
Output the only number - maximal possible quantity of defeated creeps.