Problem
Risotto Nero は、磁力のある建設業者から家を集めるのが大好きです。
n 個のパーツがあり、i 番目のパーツのサイズは s
i です。
家を建てるには、正確に
a 個の同じサイズのパーツと、正確に
b 個の同じサイズのパーツ (k 倍) が必要です。
Risotto Nero が建てることができる家の最大数を決定します。
入力:
最初の行には整数 n、a、b、k (1 ≤ n, a, b ≤ 300000, 2 ≤ k ≤ 1000) が含まれます。
2 行目には、一連のパーツ サイズが含まれています。整数 s
1, s
2, …, s
n (1 ≤ s
i ≤ 10 < sup>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] のパーツから 2 つの家を建て、寸法 [3, 6, 6] のパーツから 1 つの家を建てるのが最適なオプションです。