桌上有 $$$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$$$ 给定玩家组成的最大团队数。
示例
输入 #1
12 1 2 2 1 1 2 2 2 2 2 3 3 4 6 6
输出 #1
3
输入 #2
14 1 1 3 3 3 1 1 9 9 2 3 6 6 3 18 3 18
输出 #2
6
输入 #3
1 2 3 10 1000000
输出 #3
0