D. Команды
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Есть $$$n$$$ игроков в настольный боулинг, рейтинг $$$i$$$-го игрока равен $$$r_i$$$. Требуется составить наибольшее количество команд таким образом, чтобы:

  • каждый игрок принадлежал не более чем одной команде;
  • каждая команда состояла ровно из $$$a+b$$$ игроков;
  • в каждой команде было бы ровно $$$a$$$ игроков какого-то одинакового рейтинга и ровно $$$b$$$ игроков другого одинакового рейтинга, который в $$$k$$$ раз больше.

Например, если $$$n=12$$$, $$$r=[1, 1, 2, 2, 2, 2, 2, 3, 3, 4, 6, 6]$$$, $$$a=1$$$, $$$b=2$$$, $$$k=2$$$, то можно составить две команды с рейтингами $$$[1, 2, 2]$$$ и одну с рейтингами $$$[3, 6, 6]$$$. Таким образом, максимум можно составить $$$3$$$ команды.

По заданным $$$n, r_1 \dots r_n, a, b$$$ и $$$k$$$ найдите максимальное количество команд, которое можно составить.

Входные данные

В первой строке записаны целые числа $$$n$$$, $$$a$$$, $$$b$$$ и $$$k$$$ ($$$1 \le n,a,b \le 3\cdot10^5$$$, $$$2 \le k \le 1000$$$). Вторая строка содержит последовательность рейтингов игроков — целые числа $$$r_1, r_2, \dots, r_n$$$ ($$$1 \le r_i \le 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