← 返回题目列表

Codeforces · 1671/C

C. 甜蜜生活

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

动荡的时代即将来临,所以你决定提前买糖。周围有 $$$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$$$ 包。