Problem
Risotto Nero ama collezionare case da un costruttore magnetico.
Ha n parti, la dimensione dell'i-esima è s
i.
Per costruire una casa, hai bisogno esattamente di
a parti di una dimensione identica ed esattamente di
b parti di un'altra dimensione identica, che è k volte più grande.
Determina il numero massimo di case che Risotto Nero può costruire.
Inserimento:
La prima riga contiene gli interi n, a, b e k (1 ≤ n, a, b ≤ 300000, 2 ≤ k ≤ 1000).
La seconda riga contiene la sequenza delle dimensioni delle parti — interi s
1, s
2, …, s
n (1 ≤ s
i ≤ 10 < sup>6).
Uscita:
Stampa un singolo numero intero — il numero massimo di case che possono essere costruite da n parti date.
Esempi:
| Input |
Uscita |
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 |
Spiegazione:
Nel primo esempio, l'opzione migliore è costruire due case da parti di dimensioni [1, 2, 2] e una casa da parti di dimensioni [3, 6, 6].