Ризотто Нэро любит собирать домики из магнитного конструктора.
У него есть n деталей, размер i-ой равен s
i.
Для того, чтобы построить домик, необходимо ровно
a деталей какого-то одинакового размера и ровно
b деталей другого одинакового размера, который в k раз больше.
Определите максимальное количество домиков, которое сможет построить Ризотто Нэро.
Входные данные:
В первой строке записаны целые числа n, a, b и k (1 ≤ n, a, b ≤ 300000, 2 ≤ k ≤ 1000).
Вторая строка содержит последовательность размеров деталей — целые числа s
1, s
2, …, s
n (1 ≤ s
i ≤ 10
6).
Выходные данные:
Выведите единственное целое число — максимальное количество домиков, которое можно построить из n заданных деталей.
Примеры:
| Входные данные |
Выходные данные |
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 |
Пояснение:
В первом примере оптимальным вариантом является построить два домика из деталей с размерами [1, 2, 2] и один домик из деталей с размерами [3, 6, 6].