动荡的时代即将来临,所以你决定提前买糖。周围有 $$$n$$$ 商店出售糖:第 $$$i$$$ 商店以 $$$a_i$$$ 硬币的价格出售一包糖,但每天只向一位顾客出售一包糖。因此,为了购买几包,您需要访问几家商店。
另一个问题是价格每天都在上涨:第一天的成本为 $$$a_i$$$,第二天的成本为 $$$a_i + 1$$$,第三天的成本为 $$$a_i + 2$$$,依此类推,每个商店 $$$i$$$。
相反,您的日常预算只有 $$$x$$$ 硬币。换句话说,每天你去购买尽可能多的包,总成本不超过$$$x$$$。请注意,如果您在一天内没有花费一定数量的硬币,则在接下来的几天里您将无法使用这些硬币。
最终,每包的成本将超过 $$$x$$$,并且你甚至无法购买单个包。那么,在那一刻之前您总共可以购买多少包?
输入
第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,请打印一个整数 - 在价格超出您的日常预算之前您可以购买的包总数。
示例
输入 #1
4 3 7 2 1 2 5 9 10 20 30 40 50 1 1 1 2 1000 1 1
输出 #1
11 0 1 1500
注意
在第一个测试用例中,
- 第 1 天:价格为 $$$[2, 1, 2]$$$。您可以购买所有 $$$3$$$ 包,从 $$$2 + 1 + 2 \le 7$$$ 开始。
- 第 2 天:价格为 $$$[3, 2, 3]$$$。您无法购买所有 $$$3$$$ 包,因为 $$$3 + 2 + 3 > 7$$$,因此您只能购买 $$$2$$$ 包。
- 第 3 天:价格为 $$$[4, 3, 4]$$$。您可以购买 $$$2$$$ 包,价格为 $$$4$$$ 和 $$$3$$$。
- 第 4 天:价格为 $$$[5, 4, 5]$$$。您无法再购买 $$$2$$$ 包,因此您只能购买 $$$1$$$ 包。
- 第 5 天:价格为 $$$[6, 5, 6]$$$。您可以购买 $$$1$$$ 包。
- 第 6 天:价格为 $$$[7, 6, 7]$$$。您可以购买 $$$1$$$ 包。
- 第 7 天:价格为 $$$[8, 7, 8]$$$。您仍然可以购买 $$$1$$$ 包,成本 $$$7$$$。
- 第 8 天:价格为 $$$[9, 8, 9]$$$。物价太高了,什么都买不到。
在第二个测试用例中,即使在第一天价格也太高,所以你买不到任何东西。
在第三个测试用例中,您在第一天只能购买一包。
在第四个测试用例中,您可以在前 $$$500$$$ 天购买 $$$2$$$ 包。 $$$501$$$ 天的价格为 $$$[501, 501]$$$,因此您在接下来的 $$$500$$$ 天只能购买 $$$1$$$ 包。在 $$$1001$$$ 当天,价格为 $$$[1001, 1001]$$$,因此无法再购买。您总共购买了 $$$500 \cdot 2 + 500 \cdot 1 = 1500$$$ 包。