做月饼

问题描述

猪猪带着幼儿园的小猪们做月饼！圆圆的月饼可以看作是圆柱体。小猪们准备了各种各样的馅料，他们想在月饼不“鼓胀”的前提下尽可能塞进更多不同种类的馅料。你能帮他数一数，最多能放多少种吗？

将一个月饼视作圆柱体，底面半径为 $r$、高为 $h$。月饼皮会占用体积 $x$，现有 $n$ 种馅料，其中第 $i$ 种馅料占用体积为整数 $a_i$。

月饼皮占用的体积不可忽略。每种馅料最多使用一次，问在不超过月饼总体积的前提下，最多能放入多少种馅料。

为避免浮点误差，本题固定使用如下有理数近似作为圆周率： $$\pi^{*}=\dfrac{314159265}{10^8}$$

也就是说，月饼的体积计算公式为：

$$\pi^{*}\cdot r^2\cdot h$$

输入格式

第一行包含四个整数 $n, r, h, x$。

第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

输出格式

输出一个整数，表示最多能放入的馅料种类数。

5 2 3 1
2 3 1 5 4

5

• 对于所有测试数据：$1\le n\le 100000$，$1\le r,h\le 10^6$，$0\le x\le \lfloor \pi^{*}\cdot r^2\cdot h\rfloor$，$1\le a_i\le 10^9$。