The only difference between the easy and hard versions are the locations you can teleport to.

Consider the points $0, 1, \dots, n$ on the number line. There is a teleporter located on each of the points $1, 2, \dots, n$. At point $i$, you can do the following:

Move left one unit: it costs $1$ coin.

Move right one unit: it costs $1$ coin.

Use a teleporter at point $i$, if it exists: it costs $a_i$ coins. As a result, you teleport to point $0$. Once you use a teleporter, you can't use it again.

You have $c$ coins, and you start at point $0$. What's the most number of teleporters you can use?


-----Input-----

The input consists of multiple test cases. The first line contains an integer $t$ ($1 \leq t \leq 1000$) — the number of test cases. The descriptions of the test cases follow.

The first line of each test case contains two integers $n$ and $c$ ($1 \leq n \leq 2\cdot10^5$; $1 \leq c \leq 10^9$)  — the length of the array and the number of coins you have respectively.

The following line contains $n$ space-separated integers $a_1, a_2, \dots, a_n$ ($1 \leq a_i \leq 10^9$) — the costs to use the teleporters.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot10^5$.


-----Output-----

For each test case, output the maximum number of teleporters you can use.


-----Examples-----

Input
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
Output
2
2
0
1
2
2
1
1
1
2


-----Note-----

In the first test case, you can move one unit to the right, use the teleporter at index $1$ and teleport to point $0$, move two units to the right and use the teleporter at index $2$. You are left with $6-1-1-2-1 = 1$ coins you don't have enough coins to use another teleporter. You have used two teleporters, so the answer is two.

In the second test case, you go four units to the right and use the teleporter to go to $0$, then go six units right and use the teleporter at index $6$ to go to $0$. The total cost will be $4+6+6+4 = 20$. You are left with $12$ coins, but it is not enough to reach any other teleporter and use it so the answer is $2$.

In the third test case, you don't have enough coins to use any teleporter, so the answer is zero.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Greedy algorithms


Solutions:
def solve():
	(n, c) = map(int, input().split())
	lst = list(map(int, input().split()))
	lst = [elem + i + 1 for (i, elem) in enumerate(lst)]
	lst.sort()
	ans = 0
	for i in range(n):
		if lst[i] <= c:
			ans += 1
			c -= lst[i]
		else:
			break
	print(ans)
t = int(input())
for _ in range(t):
	solve()


def tt(n, c, a):
	for i in range(n):
		a[i] += i + 1
	a.sort()
	ans = 0
	for i in a:
		if i > c:
			break
		else:
			c -= i
			ans += 1
	return ans
t = int(input())
b = []
for i in range(t):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	b.append(tt(n, c, a))
for i in b:
	print(i)


def oi():
	return int(input())

def ti():
	return map(int, input().split())

def mi():
	return list(map(int, input().split()))

def solve():
	(length, c) = ti()
	arr = mi()
	for (i, num) in enumerate(arr):
		arr[i] = num + i + 1
	arr.sort()
	ans = 0
	p = 0
	while c > 0:
		if len(arr) == p:
			break
		if c >= arr[p]:
			c -= arr[p]
			ans += 1
			p += 1
		else:
			break
	print(ans)
for _ in range(oi()):
	solve()


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr1 = sorted([i + j for (i, j) in enumerate(arr, 1)])
	ans = 0
	i = 0
	while i < n and 0 <= c - arr1[i]:
		c -= arr1[i]
		ans += 1
		i += 1
	print(ans)


for i in range(int(input())):
	(n, c) = map(int, input().split())
	l = list(map(int, input().split()))
	place = [x for x in range(1, n + 1)]
	cost = [x + y for (x, y) in zip(l, place)]
	cost.sort()
	cnt = 0
	sum = 0
	for i in cost:
		if sum + i <= c:
			sum += i
			cnt += 1
		else:
			break
	print(cnt)


import sys, math, bisect, collections, itertools, heapq
from collections import defaultdict, deque
sys.setrecursionlimit(50000)
t = int(sys.stdin.readline())
for _ in range(t):
	(n, c) = map(int, sys.stdin.readline().split())
	l = list(map(int, sys.stdin.readline().split()))
	for i in range(n):
		l[i] += i + 1
	l.sort()
	ans = 0
	for i in l:
		c -= i
		if c >= 0:
			ans += 1
		else:
			break
	print(ans)


operations_amount = int(input())
max_amounts = []
for i in range(operations_amount):
	(teleports_amount, money) = list(map(int, input().split(' ')))
	teleport = tuple(map(int, input().split(' ')))
	advanced_teleport = [num + elem + 1 for (num, elem) in enumerate(teleport)]
	advanced_teleport.sort()
	t = 0
	money_spent = 0
	for teleport_cost in advanced_teleport:
		money_spent += teleport_cost
		if money_spent > money:
			break
		t += 1
	max_amounts.append(t)
for max_amount in max_amounts:
	print(max_amount)


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	ans = 0
	costs = sorted([i + 1 + v for (i, v) in enumerate(a)])
	for p in costs:
		if c >= p:
			ans += 1
			c -= p
		else:
			break
	print(ans)


from typing import List

def pop() -> None:
	(tty, uix) = map(int, input().split())
	arr: List[int] = list(map(int, input().split()))
	for i in range(tty):
		arr[i] += i + 1
	arr.sort()
	op = 0
	while op < tty:
		if uix >= arr[op]:
			uix -= arr[op]
		else:
			break
		op += 1
	print(op)

def main() -> None:
	z = int(input())
	for i in range(z):
		pop()
main()


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	x = list(map(int, input().split()))
	x = [x[i] + i + 1 for i in range(n)]
	x.sort()
	i = 0
	while i < n and x[i] <= m:
		m -= x[i]
		i += 1
	print(i)


def print_max_tele(n, c, arr):
	arr = sorted(arr)
	count = 0
	for i in range(n):
		if arr[i] <= c:
			count += 1
			c = c - arr[i]
		else:
			break
	print(count)

def main():
	t = int(input())
	for i in range(t):
		(n, c) = map(int, input().split())
		arr = input().split()
		for i in range(n):
			arr[i] = int(arr[i]) + i + 1
		print_max_tele(n, c, arr)
main()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	bits = list(map(int, input().split()))
	s = [bits[i] + i + 1 for i in range(n)]
	s.sort()
	c = 0
	ct = 0
	for i in range(n):
		ct += s[i]
		if ct > m:
			break
		else:
			c += 1
	print(c)


def Teleporters(a, endvalue, coins):
	i = 0
	num_telep = 0
	for (i, val) in enumerate(a):
		a[i] = i + val + 1
	a = sorted(a)
	for i in a:
		if coins - i >= 0:
			coins -= i
			num_telep += 1
		else:
			return num_telep
	return num_telep
val = int(input())
result = [] * val
for i in range(val):
	(val2, coins) = map(int, input().split())
	a = list(map(int, input().split()))
	result.append(Teleporters(a, val2, coins))
for res in result:
	print(res)


def minimum_teleports(a, c, n):
	actual_cost = [a[i] + i + 1 for i in range(n)]
	actual_cost = sorted(actual_cost)
	rem_cost = c
	counter = 0
	for cost in actual_cost:
		if cost > rem_cost:
			break
		rem_cost -= cost
		counter += 1
	return counter
t = int(input().strip())
for _ in range(t):
	(n, c) = list(map(int, input().rstrip().split()))
	a = list(map(int, input().rstrip().split()))
	ans = minimum_teleports(a, c, n)
	print(ans)


def solve():
	(n, c) = map(int, input().split())
	a = [int(x) for x in input().split()]
	for i in range(n):
		a[i] += i + 1
	a.sort()
	a += [c]
	ans = 0
	while a[ans] <= c:
		c -= a[ans]
		ans += 1
	print(ans)
t = int(input())
for _ in range(t):
	solve()


from operator import add
import itertools
t = input()

def solve(a, n, c):
	p = [x + i + 1 for (i, x) in enumerate(a)]
	p.sort()
	s = itertools.accumulate(p, add)
	for (i, v) in enumerate(s):
		if v > c:
			return i
	return n
for _ in range(int(t)):
	(n, c) = map(int, input().split(' '))
	a = [*map(int, input().split(' '))]
	print(solve(a, n, c))


def solve(a, c):
	a1 = a.copy()
	for ni in range(len(a1)):
		a1[ni] += 1 + ni
	a1.sort()
	res = 0
	for ni in range(len(a1)):
		if a1[ni] > c:
			break
		res += 1
		c -= a1[ni]
	return res
t = int(input())
ans = []
for ti in range(t):
	(n, c) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	ans.append(solve(a, c))
for a in ans:
	print(a)


def start():
	(n, c) = map(int, input().split())
	arr = list(map(int, input().split()))
	mass = [arr[i] + i + 1 for i in range(n)]
	mass.sort()
	ans = 0
	while ans < n and c >= mass[ans]:
		c = c - mass[ans]
		ans = ans + 1
	print(ans)
t = int(input())
while t != 0:
	t -= 1
	start()


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	for i in range(n):
		l[i] += i + 1
	l1 = sorted(l)
	ans = 0
	for i in range(n):
		if k >= l1[i]:
			k -= l1[i]
			ans += 1
		else:
			break
	print(ans)


for i in '0' * int(input()):
	(n, m) = map(int, input().split())
	l = list(map(int, input().split()))
	for j in range(n):
		l[j] += j + 1
	l.sort()
	f = 0
	for j in l:
		if j <= m:
			m -= j
			f += 1
	print(f)


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	elem = list(map(int, input().split()))
	for i in range(n):
		elem[i] = elem[i] + i + 1
	elem.sort()
	res = 0
	cnt = 0
	for i in range(n):
		res += elem[i]
		if res > c:
			break
		cnt += 1
	print(cnt)


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	arr = list(map(int, input().split()))
	cost = [arr[i] + i + 1 for i in range(n)]
	count = 0
	for s in sorted(cost):
		c -= s
		if c < 0:
			break
		count += 1
	print(count)


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] += i + 1
	a = sorted(a)
	answ = 0
	i = 0
	while c >= a[i]:
		c -= a[i]
		answ += 1
		i += 1
		if answ == n:
			break
	print(answ)


n = int(input())
while n > 0:
	(m, c) = map(int, input().split())
	arr = list(map(int, input().split()))
	arr = [arr[i] + i + 1 for i in range(m)]
	arr.sort()
	ans = 0
	for i in arr:
		c -= i
		if c < 0:
			break
		else:
			ans += 1
	print(ans)
	n -= 1


import sys
import collections
from math import ceil, gcd, sqrt, log
import bisect
import heapq
INF = float('inf')
mod = 1000000007

def solve():
	(n, c) = map(int, input().split())
	A = list(map(int, input().split()))
	minHeap = []
	for i in range(n):
		heapq.heappush(minHeap, A[i] + i + 1)
	net = 0
	while minHeap and c >= minHeap[0]:
		c -= heapq.heappop(minHeap)
		net += 1
	print(net)
t = int(input())
while t != 0:
	solve()
	t -= 1


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	c2 = 1
	for i in range(n):
		a[i] += c2
		c2 += 1
	a.sort()
	s = 0
	c1 = 0
	for j in range(n):
		s += a[j]
		if s <= c:
			c1 += 1
		else:
			break
	print(c1)


for _ in range(int(input())):
	(n, pre) = map(int, input().split())
	arr = list(map(int, input().split()))
	for i in range(n):
		arr[i] += i + 1
	arr.sort()
	i = 0
	while i < n:
		if pre < arr[i]:
			break
		pre -= arr[i]
		i += 1
	print(i)


t = int(input())
for _ in range(t):
	(n, money) = map(int, input().split())
	costs = list(map(int, input().split()))
	for i in range(n):
		costs[i] += i + 1
	flag = True
	costs.sort()
	gross = 0
	for i in range(n):
		gross += costs[i]
		if gross > money:
			flag = False
			break
	print(i + flag)


t = int(input())
for _ in range(t):
	(n, c) = map(int, input().split())
	vet = list(map(int, input().split()))
	for i in range(n):
		vet[i] += i + 1
	vet = sorted(vet)
	port = 0
	for i in range(n):
		if c >= vet[i]:
			c -= vet[i]
			port += 1
		else:
			break
	print(port)


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	list1 = list(map(int, input().split()))
	nums = []
	for i in range(len(list1)):
		nums.append(list1[i] + i + 1)
	nums.sort()
	count = 0
	for i in range(len(nums)):
		c -= nums[i]
		if c >= 0:
			count += 1
		else:
			break
	print(count)


for x in range(int(input())):
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	for x in range(len(b)):
		b[x] = b[x] + x + 1
	b.sort()
	c = 0
	d = 0
	k = True
	for x in b:
		e = c + x
		if e > a[1]:
			print(d)
			k = False
			break
		else:
			c = e
			d += 1
	if k:
		print(d)


import sys

def answer():
	pass

def solution():
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] += i + 1
	a.sort()
	k = 0
	for i in a:
		if c < i:
			print(k)
			break
		c -= i
		k += 1
	else:
		print(n)
t = int(input())
for _ in range(t):
	solution()


T = int(input())
for _ in range(T):
	(a, b) = map(int, input().split())
	arr = list(map(int, input().split()))
	for i in range(a):
		arr[i] += i + 1
	arr.sort()
	sum_ = 0
	counter = 0
	for i in range(a):
		if sum_ + arr[i] <= b:
			sum_ += arr[i]
			counter += 1
		else:
			break
	print(counter)


import sys
for _ in range(int(next(sys.stdin))):
	input = next(sys.stdin).split(' ')
	n = int(input[0])
	c = int(input[1])
	a = next(sys.stdin).strip().split(' ')
	a = list((int(i) for i in a))
	for i in range(n):
		a[i] += i + 1
	a.sort()
	res = 0
	for i in a:
		c -= i
		if c < 0:
			break
		res += 1
	print(res)


tasks = int(input())
for t in range(tasks):
	(ts, m) = map(int, input().split())
	arr = list(map(int, input().split()))
	for i in range(ts):
		arr[i] += i + 1
	arr.sort()
	c = 0
	flag = True
	for i in range(ts):
		m -= arr[i]
		if m >= 0:
			c += 1
		else:
			print(c)
			flag = False
			break
	if flag:
		print(c)


def number(a, n, p, k):
	a.sort()
	pre = []
	for i in range(n):
		pre.append(0)
	ans = 0
	val = 0
	i = 0
	j = 0
	pre[0] = a[0]
	if pre[0] <= p:
		ans = 1
	for i in range(1, k - 1):
		pre[i] = pre[i - 1] + a[i]
		if pre[i] <= p:
			ans = i + 1
	pre[k - 1] = a[k - 1]
	for i in range(k - 1, n):
		if i >= k:
			pre[i] += pre[i - k] + a[i]
		if pre[i] <= p:
			ans = i + 1
	return ans
for t in range(int(input())):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] += i + 1
	a.sort()
	ans = 0
	ct = 0
	for i in a:
		if i + ans > c:
			break
		ans += i
		ct += 1
	print(ct)


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	for i in range(1, n + 1):
		l[i - 1] += i
	l.sort()
	i = 0
	while i < n:
		k -= l[i]
		if k < 0:
			break
		else:
			i += 1
	print(i)


num_cases = int(input())
for _ in range(num_cases):
	(num_elements, num_coins) = input().split()
	(num_elements, num_coins) = (int(num_elements), int(num_coins))
	arr = list(map(int, input().split()))
	if num_elements == 0:
		print(0)
		break
	for i in range(1, num_elements + 1):
		arr[i - 1] += i
	arr.sort()
	i = 0
	teles_used = 0
	while i < num_elements and num_coins >= arr[i]:
		num_coins -= arr[i]
		i += 1
		teles_used += 1
	print(teles_used)


for i in range(int(input())):
	(n, c) = map(int, input().split())
	l = list(map(int, input().split()))
	for i in range(n):
		l[i] = l[i] + i + 1
	l = sorted(l)
	ans = 0
	for i in range(n):
		if c >= l[i]:
			c = c - l[i]
			ans = ans + 1
		else:
			break
	print(ans)


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	count = 0
	for i in range(n):
		a[i] += i + 1
	a.sort()
	for x in a:
		if x <= c:
			c -= x
			count += 1
		else:
			break
	print(count)


n = int(input())

def check(c, arr):
	res = 0
	arr = [arr[i] + i + 1 for i in range(len(arr))]
	arr.sort()
	for i in arr:
		if i <= c:
			res += 1
			c -= i
		else:
			break
	return res
for i in range(n):
	c = [int(i) for i in input().split(' ')][1]
	arr = [int(i) for i in input().split(' ')]
	print(check(c, arr))


for i in range(int(input())):
	(n, c) = map(int, input().split())
	l = list(map(int, input().split()))
	for j in range(n):
		l[j] = l[j] + j + 1
	l.sort()
	cnt = 0
	s = 0
	while s <= c and cnt < n:
		s += l[cnt]
		cnt += 1
	if s > c:
		print(cnt - 1)
	else:
		print(cnt)


def min_coins_to_reach_teleporter(arr, n, coins):
	arr.sort(reverse=True)
	teleporters = 0
	while len(arr) > 0 and coins >= arr[-1]:
		teleporters += 1
		coins -= arr[-1]
		arr.pop()
	return teleporters

def teleporters(n, coins, arr):
	cost = []
	for i in range(n):
		cost.append(arr[i] + i + 1)
	return min_coins_to_reach_teleporter(cost, n, coins)

def main():
	t = int(input().strip())
	for i in range(t):
		(n, coins) = map(int, input().strip().split())
		arr = list(map(int, input().strip().split()))
		print(teleporters(n, coins, arr))
main()


t = int(input())
for _ in range(t):
	(a, b) = map(int, input().split())
	mylist = list(map(int, input().split()))
	for iamsuperman in range(a):
		mylist[iamsuperman] += iamsuperman + 1
	mylist.sort()
	cnt = 0
	for iamspiderman in range(a):
		if b >= mylist[iamspiderman]:
			b -= mylist[iamspiderman]
			cnt += 1
		else:
			break
	print(cnt)


for _ in range(int(input())):
	(n, c) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] += i + 1
	a.sort()
	r = 0
	id = 0
	while True:
		if id > n - 1:
			break
		elif a[id] <= c:
			r += 1
			c -= a[id]
			id += 1
		else:
			break
	print(r)


t = int(input())
for k in range(t):
	(n, c) = map(int, input().split())
	a = sorted([int(j) + i + 1 for (i, j) in enumerate(input().split())])
	s = 0
	for i in a:
		if c >= i:
			c -= i
			s += 1
		else:
			break
	print(s)


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	print(len([(c := (c - j)) for j in sorted([int(i) + values + 1 for (values, i) in enumerate(input().split())]) if c - j >= 0]))


t = int(input())
maj = []
for i in range(t):
	numb = [int(num) for num in input().split(' ', 1)]
	mino = [int(num) for num in input().split(' ', numb[0] - 1)]
	mas = []
	mas.append(mino)
	mas.append([numb[1]])
	maj.append(mas)

def pri(c, l):
	for i in range(len(l)):
		l[i] = l[i] + (i + 1)
	l = sorted(l)
	p = 0
	j = 0
	count = 0
	while p < c:
		if j == len(l):
			break
		p += l[j]
		j += 1
		count += 1
	if p <= c:
		print(count)
	else:
		print(count - 1)
for i in maj:
	l = i[0]
	c = i[1][0]
	pri(c, l)


t = int(input())
while t > 0:
	t -= 1
	(n, c) = [int(x) for x in input().split()]
	a = [int(x) for x in input().split()]
	counter = 0
	for y in sorted([a[i] + i + 1 for i in range(n)]):
		if c - y >= 0:
			counter = counter + 1
			c -= y
		else:
			break
	print(counter)


t = int(input())
for i in range(t):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] += i + 1
	a.sort()
	ans = 0
	for i in range(n):
		if a[i] <= c:
			c -= a[i]
			ans += 1
		else:
			break
	print(ans)


from sys import stdin
from heapq import heappush, heappop
t = int(stdin.readline())
all_ans = []
for _ in range(t):
	(n, c) = map(int, stdin.readline().split())
	pq = []
	for (idx, cost) in enumerate(stdin.readline().split()):
		heappush(pq, int(cost) + idx + 1)
	ans = 0
	while pq and c >= pq[0]:
		ans += 1
		c -= heappop(pq)
	all_ans.append(ans)
print('\n'.join(map(str, all_ans)))


t = int(input())
for t1 in range(t):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] += i + 1
	count = 0
	sum = 0
	a.sort()
	for i in range(n):
		sum += a[i]
		if sum <= c:
			count += 1
		else:
			break
	print(count)


def solve():
	num_tests = int(input())
	for i in range(num_tests):
		coin_input = input()
		space_input = input()
		coin_list = []
		space_list = []
		for j in coin_input.split(' '):
			coin_list.append(int(j))
		for j in space_input.split(' '):
			space_list.append(int(j))
		length = coin_list[0]
		coins = coin_list[1]
		for j in range(length):
			space_list[j] += j + 1
		space_list.sort()
		count = 0
		for j in space_list:
			coins -= j
			if coins >= 0:
				count += 1
		print(count)
solve()


t = int(input())
for i in range(t):
	(n, c) = map(int, input().split())
	l = list(map(int, input().split()))
	L = []
	for i in range(len(l)):
		L.append(i + 1 + l[i])
	L.sort()
	s = 0
	result = 0
	complete = -1
	for k in range(len(L)):
		complete = k
		s += L[k]
		if s >= c:
			complete = -1
			if s == c:
				result = k + 1
			else:
				result = k
			break
	if result >= 0 and complete == -1:
		print(result)
	elif complete >= 0:
		print(complete + 1)


out = []
for _ in range(int(input())):
	(n, c) = map(int, input().split())
	a = [int(i) for i in input().split()]
	for i in range(n):
		a[i] += i + 1
	a.sort()
	ans = 0
	for i in a:
		if i <= c:
			ans += 1
			c -= i
		else:
			break
	out.append(ans)
for i in out:
	print(i)


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	for x in range(1, 1 + n):
		lst[x - 1] += x
	lst.sort()
	rslt = x = 0
	while x < n and k - lst[x] >= 0:
		k -= lst[x]
		x += 1
		rslt += 1
	print(rslt)


T = int(input())
for _ in range(T):
	(n, c) = [int(_) for _ in input().split()]
	a = [int(_) for _ in input().split()]
	b = []
	for i in range(n):
		b.append(i + a[i] + 1)
	b = sorted(b)
	res = 0
	for x in b:
		if c < x:
			break
		c -= x
		res += 1
	print(res)


def solve():
	(n, c) = list(map(int, input().split()))
	a = list(map(int, input().split()))
	real_cost = [0 for i in range(n)]
	for i in range(n):
		real_cost[i] = a[i] + i + 1
	real_cost.sort()
	ans = 0
	for i in range(n):
		if c - real_cost[i] < 0:
			break
		c -= real_cost[i]
		ans += 1
	print(ans)
t = int(input())
for _ in range(t):
	solve()


for _ in range(int(input())):
	(n, c) = list(map(int, input().split()))
	lis = list(map(int, input().split()))
	lis = sorted([lis[i] + 1 + i for i in range(len(lis))])
	k = 0
	count = 0
	while k <= c and count < len(lis):
		k += lis[count]
		count += 1
	if k > c:
		count -= 1
	print(count)


import sys
input = sys.stdin.readline
test_cases = int(input())
inputs = []

def inlt():
	return list(map(int, input().split()))

def actual_cost(arr):
	res = []
	for i in range(len(arr)):
		res.append(i + 1 + arr[i])
	return res
for i in range(test_cases):
	line1 = inlt()
	a_length = line1[0]
	coins = line1[1]
	arr = inlt()
	inputs.append({'arr': arr, 'coins': coins})
for val in inputs:
	cost_arr = actual_cost(val['arr'])
	coins = val['coins']
	cost_arr.sort()
	ans = 0
	for cost in cost_arr:
		coins = coins - cost
		if coins < 0:
			break
		else:
			ans += 1
	print(ans)


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	a = list(map(lambda x: x[0] + int(x[1]), enumerate(input().split(), 1)))
	a.sort()
	cnt = 0
	for i in a:
		if c >= i:
			cnt += 1
			c -= i
		else:
			break
	print(cnt)


for _ in range(int(input())):
	(n, q) = map(int, input().split())
	a = list(map(int, input().split()))
	lst = []
	for i in range(n):
		lst.append(i + 1 + a[i])
	lst = sorted(lst)
	c = 0
	s = 0
	for i in range(n):
		s += lst[i]
		if s <= q:
			c += 1
		else:
			break
	print(c)


def solution(arr, length, q):
	for i in range(length):
		arr[i] += i + 1
	arr.sort()
	res = 0
	for i in arr:
		q -= i
		if q >= 0:
			res += 1
		else:
			break
	return res
case = int(input())
for _ in range(case):
	(length, queries) = list(map(int, input().split(' ')))
	nums = list(map(int, input().split(' ')))
	print(solution(nums, length, queries))


t = int(input())
while t:
	t -= 1
	(n, c) = map(int, input().split())
	a = [0] + list(map(int, input().split()))
	v = []
	for i in range(1, n + 1):
		v.append(a[i] + i)
	v.sort()
	cnt = 0
	for i in range(n):
		if c >= v[i]:
			cnt += 1
			c -= v[i]
		else:
			break
	print(cnt)


import heapq
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] += i + 1
	heapq.heapify(a)
	count = 0
	while m >= 0:
		if len(a) == 0:
			count += 1
			break
		c = heapq.heappop(a)
		m -= c
		count += 1
	print(count - 1)


tests = int(input())
for _ in range(tests):
	(lgth, my_coins) = map(int, input().split())
	coins = list(map(int, input().split()))
	for j in range(lgth):
		coins[j] += j + 1
	coins.sort()
	_sum = 0
	answer = -1
	i = 0
	while i < lgth:
		_sum += coins[i]
		if _sum > my_coins:
			break
		answer = i
		i += 1
	print(answer + 1)


t = int(input())
for _ in range(t):
	(n, c) = [int(x) for x in input().split()]
	teleporters = [int(x) for x in input().split()]
	moveTeleportCost = sorted([x + i + 1 for (i, x) in enumerate(teleporters)])
	maxUse = 0
	for t in moveTeleportCost:
		c -= t
		if c >= 0:
			maxUse += 1
		else:
			break
	print(maxUse)


def solve():
	(num_of_stops, fuel) = map(int, input().split())
	stops = [int(x) for x in input().split()]
	for i in range(num_of_stops):
		stops[i] += i + 1
	stops.sort()
	num_of_stops_covered = 0
	while num_of_stops_covered < num_of_stops and fuel >= stops[num_of_stops_covered]:
		fuel -= stops[num_of_stops_covered]
		num_of_stops_covered += 1
	print(num_of_stops_covered)
num_of_test_cases = int(input().strip())
for _ in range(num_of_test_cases):
	solve()


for i in range(int(input())):
	(x, y) = map(int, input().split())
	l = list(map(int, input().split()))
	for i in range(len(l)):
		l[i] += i + 1
	l.sort()
	c = 0
	for i in range(len(l)):
		if y >= l[i]:
			y -= l[i]
			c += 1
		else:
			break
	print(c)


cantidad = int(input())
for casos in range(cantidad):
	info = input().split(' ')
	n = int(info[0])
	c = int(info[1])
	lista = input().split(' ')
	precio = []
	for i in range(n):
		precio.append(1 + i + int(lista[i]))
	precio.sort()
	pagar = 0
	contador = 0
	while pagar <= c and contador < n:
		pagar += precio[contador]
		contador += 1
	if contador == n and pagar <= c:
		print(contador)
	else:
		print(contador - 1)


import sys
from typing import List

def main():
	tt = int(input().strip())
	while tt:
		tt -= 1
		(n, nums) = map(int, input().strip().split())
		arr = [int(x) for x in input().strip().split()]
		for i in range(n):
			arr[i] += i + 1
		arr.sort()
		j = 0
		for i in range(n):
			if nums >= arr[i]:
				nums -= arr[i]
				j += 1
			else:
				break
		print(j)
sys.exit(main())


for tcase in range(int(input())):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	b = [i + 1 + a[i] for i in range(n)]
	b.sort()
	i = 0
	while i < n and c >= b[i]:
		c -= b[i]
		i += 1
	print(i)


t = int(input())
for i in range(t):
	(n, coins) = map(int, input().split())
	costs = list(map(int, input().split()))
	costs = [k + costs[k] + 1 for k in range(len(costs))]
	costs.sort()
	for k in range(len(costs)):
		if coins >= costs[k]:
			coins -= costs[k]
		else:
			coins -= costs[k]
			break
	if coins >= 0:
		print(k + 1)
	else:
		print(k)


tc = int(input())
res = []
for i in range(tc):
	nc = input().split(' ')
	n = int(nc[0])
	c = int(nc[1])
	arr = input().split(' ')
	arr = [int(arr[i]) + i + 1 for i in range(len(arr))]
	arr = sorted(arr)
	i = 0
	count = 0
	while c > 0 and i < n:
		if c >= arr[i]:
			c -= arr[i]
			count += 1
			i += 1
		else:
			break
	res.append(count)
for i in res:
	print(i)


for _ in range(int(input())):
	(n, p) = map(int, input().split())
	arr = list(map(int, input().split()))
	for i in range(n):
		arr[i] += i + 1
	arr.sort()
	ans = 0
	for j in range(n):
		if p >= arr[j]:
			ans += 1
			p -= arr[j]
		else:
			break
	print(ans)


ri = lambda : int(input())
rl = lambda : list(map(int, input().split()))
rs = lambda : input()

def solve():
	(n, c) = rl()
	a = rl()
	a = [val + i + 1 for (i, val) in enumerate(a)]
	a.sort()
	ans = 0
	for val in a:
		if val <= c:
			c -= val
			ans += 1
	return ans

def main():
	for _ in range(ri()):
		print(solve())
main()


def solve():
	t = 1
	t = int(input())
	while t:
		t -= 1
		(n, c) = [int(x) for x in input().split()]
		a = [int(x) for x in input().split()]
		b = []
		t_count = 0
		for i in range(n):
			b.append(a[i] + i + 1)
		b.sort()
		for i in range(n):
			if c >= b[i]:
				c -= b[i]
				t_count += 1
			else:
				break
		print(t_count)
solve()


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	a = sorted([x + i + 1 for (i, x) in enumerate(map(int, input().split()))])
	ans = 0
	for x in a:
		if x <= c:
			c -= x
			ans += 1
	print(ans)


t = int(input())
for i in range(t):
	(N, C) = list(map(int, input().split()))
	vals = list(map(int, input().split()))
	greedy = []
	for i in range(N):
		greedy.append(1 + i + vals[i])
	greedy.sort()
	current = 0
	for i in range(len(greedy)):
		current += greedy[i]
		if current > C:
			print(i)
			break
		if i == len(greedy) - 1:
			print(len(greedy))


for _ in range(int(input())):
	(n, c) = map(int, input().split())
	a = list(map(int, input().split()))
	for i in range(n):
		a[i] = a[i] + i + 1
	a = sorted(a)
	ans = 0
	i = 0
	while i < n and c > 0:
		if a[i] <= c:
			c -= a[i]
			ans += 1
			i += 1
		else:
			break
	print(ans)


amount = int(input())
for i in range(amount):
	line = input().split(' ')
	newAmount = int(line[0])
	money = int(line[1])
	teleports = 0
	line = input().split(' ')
	paths = []
	for j in range(len(line)):
		num = int(line[j]) + j + 1
		paths.append(num)
	paths.sort()
	for j in paths:
		if money - j >= 0:
			teleports += 1
			money -= j
		else:
			break
	print(teleports)


q = int(input())
for i in range(q):
	out = 0
	xd = 0
	(delka, prachy) = map(int, input().split())
	lol = list(map(int, input().split()))
	for i in range(delka):
		lol[i] = lol[i] + 1 + i
	lol.sort()
	for i in range(len(lol)):
		xd = xd + lol[i]
		if xd > prachy:
			break
		out = out + 1
	print(out)


import math
T = int(input(''))
for i in range(T):
	str1 = input()
	l1 = [int(c) for c in str1.split()]
	str1 = input()
	l2 = [int(c) for c in str1.split()]
	coins = l1[1]
	for j in range(len(l2)):
		l2[j] += j + 1
	l2.sort()
	teleports = 0
	for element in l2:
		if element > coins:
			break
		else:
			teleports += 1
			coins -= element
	print(teleports)