C. World of Darkraft 3
time limit per test
1 second
memory limit per test
512 megabytes
input
standard input
output
standard output

Roma plays a new version of the "World of Darkraft" game as a wizard character. Roma values his time and tries to complete in-game tasks as efficient as possible.

Roma is now fighting n monsters. The i-th of these monsters has hi health points. A monster dies when his health points become zero of negative (at that moment Roma's character gains experience).

Roma's character has a pool of m mana points. The character possesses two spell abilities: "Lightning strike" and "Ring of ice".

  • "Lightning strike" spell deals ds damage to a chosen monster (that is, descreases its health points by ds), and one cast of this spell costs cs mana points.
  • "Ring of ice" spell deals da damage to all monsters still alive, and one cast of this spell costs ca mana points.

The character can not use a spell if the number of mana points left is strictly less than the cost of this spell. The battle finishes as soon as all monsters are dead, or if it is not possible to cast any of two spells (then the character needs to retreat and rest).

In this battle Roma wants to gain as much experience as possible. Help Roma determine the maximum possible number of monsters he can kill.

Input

The first line contains six integers n, m, ds, cs, da and ca (1 ≤ n, m, ds, cs, da, ca ≤ 100) — the number of monsters, the amount of characters' mana, and also damage and mana cost of "Lightning strike" and "Ring of ice" spells respectively.

The second line contains n integers h1, h2, ..., hn — monsters' health points (1 ≤ hi ≤ 100).

Output

Print one number — the maximum number of monsters that can be defeated.

Examples
Input
3 5 1 1 3 3
4 1 5
Output
2
Input
5 70 10 10 1 20
11 11 11 11 11
Output
5
Note

In the first sample, the character can cast "Ring of ice" once (as a result, the first monster will have one health point, the third monster will have two health points, and the second monster will die). After that, the character can apply "Lightning strike" twice to kill another monster.

In the second sample, the only way to defeat all monsters is to cast "Ring of ice" once, and "Lightning strike" once for each monster.