Problem
Risotto Nero adora colecionar casas de um construtor magnético.
Tem n partes, o tamanho da i-ésima é s
i.
Para construir uma casa, você precisa exatamente
a partes de algum tamanho idêntico e exatamente
b partes de outro tamanho idêntico, que é k vezes maior.
Determine o número máximo de casas que Risotto Nero pode construir.
Entrada:
A primeira linha contém os inteiros n, a, b e k (1 ≤ n, a, b ≤ 300000, 2 ≤ k ≤ 1000).
A segunda linha contém a sequência de tamanhos de peças — inteiros s
1, s
2, …, s
n (1 ≤ s
i ≤ 10 < sup>6).
Saída:
Imprima um único inteiro — o número máximo de casas que podem ser construídas a partir de n partes dadas.
Exemplos:
| Entrada |
Saída |
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 |
Explicação:
No primeiro exemplo, a melhor opção é construir duas casas com peças de dimensões [1, 2, 2] e uma casa com peças de dimensões [3, 6, 6].