CF1671C.Dolce Vita

Turbulent times are coming, so you decided to buy sugar in advance. There are $n$ shops around that sell sugar: the $i$-th shop sells one pack of sugar for $a_i$ coins, but only one pack to one customer each day. So in order to buy several packs, you need to visit several shops.

Another problem is that prices are increasing each day: during the first day the cost is $a_i$, during the second day cost is $a_i + 1$, during the third day — $a_i + 2$ and so on for each shop $i$.

On the contrary, your everyday budget is only $x$ coins. In other words, each day you go and buy as many packs as possible with total cost not exceeding $x$. Note that if you don't spend some amount of coins during a day, you can't use these coins during the next days.

Eventually, the cost for each pack will exceed $x$, and you won't be able to buy even a single pack. So, how many packs will you be able to buy till that moment in total?

动荡时期即将到来，因此你决定提前购买糖。周围共有 $n$ 家商店出售糖：第 $i$ 家商店每天仅向每位顾客出售一包糖，每包售价为 $a_i$ 枚金币。

另一个问题是，每家商店的糖价每天都会上涨：第一天价格为 $a_i$，第二天为 $a_i + 1$，第三天为 $a_i + 2$，依此类推（对每家商店 $i$ 均如此）。

相反，你每日的预算是固定的，仅为 $x$ 枚金币。换句话说，你每天都会出门，在总花费不超过 $x$ 的前提下尽可能多地购买糖包。注意：若某天未用完全部预算，剩余金币无法累积至后续日期使用。

最终，每包糖的价格都将超过 $x$，导致你连一包糖也无法再购买。那么，在此之前，你总共能买到多少包糖？

The first line contains a single integer $t$ ($1 \le t \le 1000$) — the number of test cases. Next $t$ cases follow.

The first line of each test case contains two integers $n$ and $x$ ($1 \le n \le 2 \cdot 10^5$; $1 \le x \le 10^9$) — the number of shops and your everyday budget.

The second line of each test case contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the initial cost of one pack in each shop.

It's guaranteed that the total sum of $n$ doesn't exceed $2 \cdot 10^5$.

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试用例的数量。接下来是 $t$ 个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $x$（$1 \le n \le 2 \cdot 10^5$；$1 \le x \le 10^9$），分别表示商店数量和你每日的预算。

每个测试用例的第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$1 \le a_i \le 10^9$），表示每个商店中一包商品的初始价格。

保证所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

For each test case, print one integer — the total number of packs you will be able to buy until prices exceed your everyday budget.

对于每个测试用例，输出一个整数——在价格超过您每日预算之前，您能够购买的包装总数。

In the first test case,

• Day 1: prices are $[2, 1, 2]$. You can buy all $3$ packs, since $2 + 1 + 2 \le 7$.
• Day 2: prices are $[3, 2, 3]$. You can't buy all $3$ packs, since $3 + 2 + 3 \gt 7$, so you buy only $2$ packs.
• Day 3: prices are $[4, 3, 4]$. You can buy $2$ packs with prices $4$ and $3$.
• Day 4: prices are $[5, 4, 5]$. You can't buy $2$ packs anymore, so you buy only $1$ pack.
• Day 5: prices are $[6, 5, 6]$. You can buy $1$ pack.
• Day 6: prices are $[7, 6, 7]$. You can buy $1$ pack.
• Day 7: prices are $[8, 7, 8]$. You still can buy $1$ pack of cost $7$.
• Day 8: prices are $[9, 8, 9]$. Prices are too high, so you can't buy anything.

In total, you bought $3 + 2 + 2 + 1 + 1 + 1 + 1 = 11$ packs.

In the second test case, prices are too high even at the first day, so you can't buy anything.

In the third test case, you can buy only one pack at day one.

In the fourth test case, you can buy $2$ packs first $500$ days. At day $501$ prices are $[501, 501]$, so you can buy only $1$ pack the next $500$ days. At day $1001$ prices are $[1001, 1001]$ so can't buy anymore. In total, you bought $500 \cdot 2 + 500 \cdot 1 = 1500$ packs.

在第一个测试用例中：

• 第 1 天：价格为 $[2, 1, 2]$。你可以购买全部 $3$ 包，因为 $2 + 1 + 2 \le 7$。
• 第 2 天：价格为 $[3, 2, 3]$。你无法购买全部 $3$ 包，因为 $3 + 2 + 3 \gt 7$，因此你仅购买 $2$ 包。
• 第 3 天：价格为 $[4, 3, 4]$。你可以购买价格为 $4$ 和 $3$ 的 $2$ 包。
• 第 4 天：价格为 $[5, 4, 5]$。你已无法再购买 $2$ 包，因此仅购买 $1$ 包。
• 第 5 天：价格为 $[6, 5, 6]$。你可以购买 $1$ 包。
• 第 6 天：价格为 $[7, 6, 7]$。你可以购买 $1$ 包。
• 第 7 天：价格为 $[8, 7, 8]$。你仍可购买花费为 $7$ 的 $1$ 包。
• 第 8 天：价格为 $[9, 8, 9]$。价格过高，因此你无法购买任何商品。

总计，你购买了 $3 + 2 + 2 + 1 + 1 + 1 + 1 = 11$ 包。

在第二个测试用例中，即使在第一天价格也过高，因此你无法购买任何商品。

在第三个测试用例中，你只能在第一天购买 $1$ 包。

在第四个测试用例中，前 $500$ 天每天均可购买 $2$ 包。第 $501$ 天的价格为 $[501, 501]$，因此接下来的 $500$ 天每天只能购买 $1$ 包。第 $1001$ 天的价格为 $[1001, 1001]$，此后便无法再购买任何商品。总计，你购买了 $500 \cdot 2 + 500 \cdot 1 = 1500$ 包。