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

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

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

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

У вас есть $$$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
3
0
1
3
2
1
1
2
2
Примечание

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

Во втором наборе входных данных вы перемещаетесь на четыре единицы вправо и используете телепорт, перемещаясь в $$$n+1$$$, затем перемещаетесь на три единицы влево и используете телепорт в точке $$$6$$$, перемещаясь в $$$n+1$$$, и затем перемещаетесь влево на четыре единицы и используете телепорт. Общая стоимость составит $$$4+6+3+4+4+9 = 30$$$ и вы использовали три телепорта.

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