Problem
Risotto Nero loves to collect houses from a magnetic constructor.
It has n parts, the size of the i-th one is s
i.
In order to build a house, you need exactly
a parts of some identical size and exactly
b parts of another identical size, which is k times larger.
Determine the maximum number of houses Risotto Nero can build.
Input:
The first line contains integers n, a, b and k (1 ≤ n, a, b ≤ 300000, 2 ≤ k ≤ 1000).
The second line contains the sequence of part sizes — integers s
1, s
2, …, s
n (1 ≤ s
i ≤ 10
6).
Output:
Print a single integer — the maximum number of houses that can be built from n given parts.
Examples:
| Input |
Output |
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 |
Explanation:
In the first example, the best option is to build two houses from parts with dimensions [1, 2, 2] and one house from parts with dimensions [3, 6, 6].