← 返回题目列表

Codeforces · 1334/B

B. 中产阶级

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

许多年前,伯兰是一个只有 $$$n$$$ 人居住的小国家。每个人都有一些积蓄:第 $$$i$$$ 个有 $$$a_i$$$ burles。

如果一个人至少拥有 $$$x$$$ burles,政府就会认为他是富有的。为了增加富人的数量,贝尔兰德决定进行几项改革。每项改革看起来都是这样的:

- 政府选择一些人的子集(也许是所有人);
- 政府从选定的人那里拿走所有储蓄,并在选定的人之间平等地重新分配储蓄。

例如,将储蓄视为列表 $$$[5, 1, 2, 1]$$$:如果政府选择了 $$$1$$$-st 和 $$$3$$$-rd 人员,那么它首先将获取所有 $$$5 + 2 = 7$$$ burles,然后将 $$$3.5$$$ burles 返回给所选人员。结果,节省的金额将变为 $$$[3.5, 1, 3.5, 1]$$$。

从那时起,大量数据丢失,因此我们不知道实施了多少改革以及针对谁。我们能做的就是请你计算出经过几次(也许是零)改革后,富人的最大可能数量。

输入

第一行包含单个整数 $$$T$$$ ($$$1 \le T \le 1000$$$) — 测试用例的数量。

接下来的 $$$2T$$$ 行包含测试用例 - 每个测试用例两行。第一行包含两个整数 $$$n$$$ 和 $$$x$$$ ($$$1 \le n \le 10^5$$$, $$$1 \le x \le 10^9$$$) — 人数和被视为富有的最低金额。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — 每个人的初始储蓄。

保证$$$n$$$的总和不超过$$$10^5$$$。

输出

打印 $$$T$$$ 整数 — 每个测试用例一个。对于每个测试用例,打印经过几次(可能为零)改革后富人的最大可能数量。

示例

输入 #1

4
4 3
5 1 2 1
4 10
11 9 11 9
2 5
4 3
3 7
9 4 9

输出 #1

2
4
0
3

注意

声明中描述了第一个测试用例。

在第二个测试案例中,例如,政府可以进行两项改革:$$$[\underline{11}, \underline{9}, 11, 9] \rightarrow [10, 10, \underline{11}, \underline{9}] \rightarrow [10, 10, 10, 10]$$$。

在第三个测试案例中,政府甚至无法让一个人变得富有。

在第四个测试案例中,政府可以选择所有人进行改革:$$$[\underline{9}, \underline{4}, \underline{9}] \rightarrow [7\frac{1}{3}, 7\frac{1}{3}, 7\frac{1}{3}]$$$。