G1. Телепорты (Простая версия)
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Единственное отличие между простой и сложной версиями — точки, куда вы можете телепортироваться.

Рассмотрим точки $$$0, 1, \dots, n$$$ расположенные на прямой. Имеются телепорты, расположенные в каждой из точек $$$1, 2, \dots, n$$$. В точке $$$i$$$ вы можете сделать следующее:

  • Переместиться влево на единицу. Это стоит $$$1$$$ монету.
  • Переместиться вправо на единицу. Это стоит $$$1$$$ монету.
  • Воспользоваться телепортом в точке $$$i$$$, если он существует. Это стоит $$$a_i$$$ монет. В результате, вы телепортируетесь в точку $$$0$$$. Каждым телепортом можно воспользоваться только один раз.

У вас есть $$$c$$$ монет, и вы начинаете в точке $$$0$$$. Каким наибольшим числом телепортов вы сможете воспользоваться?

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

Каждый тест содержит несколько наборов входных данных. Первая строка теста содержит целое число $$$t$$$ ($$$1 \leq t \leq 1000$$$) — количество наборов входных данных. Затем следуют описания наборов.

Первая строка каждого набора содержит два целых числа $$$n$$$ и $$$c$$$ ($$$1 \leq n \leq 2\cdot10^5$$$; $$$1 \leq c \leq 10^9$$$)  — длина массива и количество монет, которое у вас есть соответственно.

Следующая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$), разделенных пробелами — стоимости использования телепортов.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot10^5$$$.

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

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

Пример
Входные данные
10
5 6
1 1 1 1 1
8 32
100 52 13 6 9 4 100 35
1 1
5
4 5
4 3 2 1
5 9
2 3 1 4 1
5 8
2 3 1 4 1
4 3
2 3 4 1
4 9
5 4 3 3
2 14
7 5
5 600000000
500000000 400000000 300000000 200000000 100000000
Выходные данные
2
2
0
1
2
2
1
1
1
2
Примечание

В первом наборе входных данных вы можете переместиться на одну единицу вправо, использовать телепорт в точке $$$1$$$ и телепортироваться в точку $$$0$$$, переместиться на две единицы вправо и использовать телепорт в точке $$$2$$$. У вас останется $$$6-1-1-2-1 = 1$$$ монета, этого недостаточно, чтобы использовать другой телепорт. Вы использовали два телепорта, поэтому ответ — два.

Во втором наборе входных данных вы перемещаетесь на четыре единицы вправо и используете телепорт, перемещаясь в $$$0$$$, затем перемещаетесь на шесть единиц вправо и используете телепорт в точке $$$6$$$, перемещаясь в $$$0$$$. Общая стоимость составит $$$4+6+6+4 = 20$$$. У вас осталось $$$12$$$ монет, но этого недостаточно, чтобы добраться до любого другого телепорта и использовать его, поэтому ответ равен $$$2$$$.

В третьем наборе входных данных у вас недостаточно монет для использования любого телепорта, поэтому ответ равен нулю.