← 返回题目列表

Codeforces · 967/B

B. 浇水系统

中文机器翻译题面 查看原题

阿尔卡迪想要浇灌他唯一的花。不幸的是,他的浇水系统非常差,是为$$$n$$$ 花设计的,所以它看起来就像一个有$$$n$$$ 孔的管道。阿尔卡季只能使用从第一个洞流出的水。

Arkady 可以堵住一些洞,然后将 $$$A$$$ 升水倒入管道中。之后,水将从未堵塞的孔中按其大小 $$$s_1、s_2、\ldots、s_n$$$ 的大小按比例流出。换句话说,如果未堵塞的孔的尺寸总和为$$$S$$$,并且第$$$i$$$个孔没有被堵塞,则$$$\frac{s_i \cdot A}{S}$$$升水将从其中流出。

为了使第一个孔中流出至少 $$$B$$$ 升的水,Arkady 至少需要堵住多少个孔?

输入

第一行包含三个整数 $$$n$$$, $$$A$$$, $$$B$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le B \le A \le 10^4$$$) - 孔的数量,Arkady 将倒入系统的水量,以及他想要从第一个孔中取出的水量洞。

第二行包含 $$$n$$$ 整数 $$$s_1, s_2, \ldots, s_n$$$ ($$$1 \le s_i \le 10^4$$$) — 孔的大小。

输出

打印一个整数——Arkady 应堵塞的孔数。

示例

输入 #1

4 10 3
2 2 2 2

输出 #1

1

输入 #2

4 80 20
3 2 1 4

输出 #2

0

输入 #3

5 10 10
1000 1 1 1 1

输出 #3

4

注意

在第一个示例中,Arkady 应堵塞至少一个洞。之后,$$$\frac{10 \cdot 2}{6} \大约 3.333$$$ 升水将从第一个孔中流出,这适合阿尔卡迪。

在第二个例子中,即使没有堵塞任何孔,$$$\frac{80 \cdot 3}{10} = 24$$$升将从第一个孔中流出,即不少于$$$20$$$。

在第三个例子中,Arkady 必须堵住除第一个孔之外的所有孔,以使所有水从第一个孔流出。