Давным-давно Берляндия была маленькой страной, в которой проживало только $$$n$$$ человек. Каждый из них имел некоторое количество сбережений: у $$$i$$$-го человека было $$$a_i$$$ бурлей.
Правительство считало человека богатым, если у него было хотя бы $$$x$$$ бурлей. Чтобы увеличить количество богатых людей в Берляндии, решили провести несколько реформ. Каждая реформа выглядела следующим образом:
Например, представим сбережения как список $$$[5, 1, 2, 1]$$$: если правительство выбирает $$$1$$$-го и $$$3$$$-го человека, то оно, сначала заберет у них все $$$5 + 2 = 7$$$ бурлей, а потом вернет каждому по $$$3.5$$$ бурлей. В результате сбережения примут вид $$$[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$$$ чисел — по одному на набор входных данных. Для каждого набора выведите максимально возможное количество богатых людей после некоторого (возможно нулевого) количества реформ.
4 4 3 5 1 2 1 4 10 11 9 11 9 2 5 4 3 3 7 9 4 9
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}]$$$.
Название |
---|