Module: Algoritmos codiciosos

Problem

A Risotto Nero le encanta coleccionar casas de un constructor magnético.
Tiene n partes, el tamaño de la i-ésima es s_i. 
Para construir una casa, necesitas exactamente a partes de un tamaño idéntico y exactamente b partes de otro tamaño idéntico, que es k veces más grande.

Determine el número máximo de casas que Risotto Nero puede construir.

Entrada:
La primera línea contiene números enteros n, a, b y k (1 ≤ n, a, b ≤ 300000, 2 ≤ k ≤ 1000).
La segunda línea contiene la secuencia de tamaños de piezas — enteros s₁, s₂, …, s_n (1 ≤ s_i ≤ 10 < sup>6).

Salida:
Imprime un solo entero — el número máximo de casas que se pueden construir a partir de n partes dadas.

Ejemplos:
 
Explicación:
En el primer ejemplo, la mejor opción es construir dos casas a partir de partes con dimensiones [1, 2, 2] y una casa a partir de partes con dimensiones [3, 6, 6].
 

Entrada	Salida
12 1 2 2 1 1 2 2 2 2 2 3 3 4 6 6	3
14 1 1 3 3 3 1 1 9 9 2 3 6 6 3 18 3 18	6
1 2 3 10 1000000	0