C. Dolce Vita
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Наступают неспокойные времена, и поэтому вы решили закупиться сахаром про запас. В округе расположены $$$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$$$.

Выходные данные

Для каждого набора входных данных выведите одно число — суммарное количество пачек сахара, которые вы сможете приобрести, пока цены не превысят ваши возможности.

Пример
Входные данные
4
3 7
2 1 2
5 9
10 20 30 40 50
1 1
1
2 1000
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]$$$. Цены слишком высокие, и вы не можете ничего купить.
В результате вы купите $$$3 + 2 + 2 + 1 + 1 + 1 + 1 = 11$$$ пачек.

Во втором наборе, цены слишком высокие с первого дня, и вы не сможете ничего купить.

В третьем наборе, вы можете купить одну пачку только в первый день.

В четвертом наборе, вы можете покупать $$$2$$$ пачки первые $$$500$$$ дней. В день $$$501$$$ цены станут $$$[501, 501]$$$, а потому вы сможете покупать только $$$1$$$ пачку следующие $$$500$$$ дней. В день $$$1001$$$ цены станут $$$[1001, 1001]$$$ и вы больше ничего не сможете купить. В результате вы купите $$$500 \cdot 2 + 500 \cdot 1 = 1500$$$ пачек.