Problem
Risotto Nero aime collectionner les maisons d'un constructeur magnétique.
Il a n parties, la taille de la ième est s
i.
Pour construire une maison, il faut exactement
a pièces d'une taille identique et exactement
b pièces d'une autre taille identique, qui est k fois plus grande.
Déterminez le nombre maximum de maisons que Risotto Nero peut construire.
Saisie :
La première ligne contient les entiers n, a, b et k (1 ≤ n, a, b ≤ 300000, 2 ≤ k ≤ 1000).
La deuxième ligne contient la séquence des tailles de pièces — entiers s
1, s
2, …, s
n (1 ≤ s
i ≤ 10 < sup>6).
Sortie :
Imprimer un seul entier — le nombre maximum de maisons pouvant être construites à partir de n parties données.
Exemples :
| Entrée |
Sortie |
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 |
Explication :
Dans le premier exemple, la meilleure option est de construire deux maisons à partir de pièces aux dimensions [1, 2, 2] et une maison à partir de pièces aux dimensions [3, 6, 6].