The most dangerous cyborg Jenish is finally entrapped on a narrow bridge over a valley. The bridge is $N$ meters long. For convenience, position $i$ represents a portion of bridge between whose left border is at distance $i-1$ meters from left end and right border is at distance $i$ meters from left end. 
There are $N$ batteries placed at positions $1,2...N$. The $i^{th}$ one has energy $a[i]$.
There are two tanks of strength $X$ at positions $0$ and $N+1$. Initially Jenish has $0$ energy.
From now at any second $t$ starting from $1$, 
first, Jenish can select any battery placed at position $i$ such that $(t \leq i \leq N-t+1)$ and add $a[i]$ to his energy (every battery can be used atmost once).
Then both the tanks move one meter towards each other. If there are still any batteries present at positions where the tanks are heading, the battery gets destroyed. 
At any moment if Jenish's total energy is greater than or equal to $X$, he destroys both the tanks and he escapes the cops. If by the end of $\lfloor \frac {(n+1)}{2}\rfloor^{th}$ second, he can't destroy the tanks, he himself gets destroyed. Find out if he can escape.

-----Input:-----
- The first line consists of a single integer $T$, the number of test cases.
- The first line of each test case contains two space separated integers which represents $N$ and $X$ for that test case respectively.
- The second line of each test case contains $N$ space separated integers, $i^{th}$ of which represents $a[i]$.

-----Output:-----
For each test case, print in a single line, $YES$ if Jenish can escape or $NO$ if he gets destroyed.

-----Constraints:-----
- $1 \leq  X \leq 10^9$
- $0 \leq a[i] \leq 10^6$
- $ 1 \leq N \leq 10^5$
- $\Sigma$ $N$ over all the test cases does not exceed $10^5$

-----Sample Input:-----
3
4 8
5 1 4 2
3 4
3 1 2
2 7
5 5

-----Sample Output:-----
YES
YES
NO

-----Explanation-----
For test $1$, in the 1st second, first Jenish will select battery at index $1$ and then the tanks from either side will move one meter closer, thus destroying the battery at index $4$.Then, in the next second, Jenish will select battery at index $3$.Then,tanks will move one meter closer again to destroy the remaining battery at index $2$.But now, Jenish has a total energy of $9$ units which is more than enough to destroy the tanks.
For test $2$, Jenish can use batteries at index $1$ and $2$ to get a total energy of $4$ units.
For test $3$, Jenish can use batteries at index $1$ or $2$ and get a maximum of $5$ units of energy which is less than required.

Difficulty: VERY_HARD
Tags: Data structures
Skill types: Data structures

Starter code:

Solutions:
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	t = 2
	f = []
	flag = 0
	if x >= sum(a):
		print('NO')
		continue
	f.append(max(a[-1], a[0]))
	while t <= (n + 1) // 2:
		b = a[t - 1:n - t + 1]
		d = max(b[0], b[-1])
		e = min(b[0], b[-1])
		ind = 0
		flag1 = 0
		for i in range(len(f)):
			if f[i] < d:
				continue
			else:
				flag1 = 1
				ind = i
				f.insert(ind, d)
				a[b.index(d) + t - 1] = 0
				break
		if flag1 == 0:
			f.append(d)
			a[b.index(d) + t - 1] = 0
			ind = len(f)
		flag2 = 0
		for i in range(ind):
			if f[i] < e:
				flag2 = 1
				f.remove(f[i])
				break
		if flag2 == 1:
			flag3 = 0
			for i in range(len(f)):
				if f[i] < e:
					continue
				else:
					flag3 = 1
					inde = i
					f.insert(inde, e)
					a[len(b) - 1 + t - 1] = 0
					break
			if flag3 == 0:
				f.append(e)
				a[len(b) - 1 + t - 1] = 0
				inde = len(f)
		t += 1
		if sum(f) >= x:
			flag = 1
			print('YES')
			break
	if flag == 0:
		if sum(f) >= x:
			print('YES')
		else:
			print('NO')


import heapq
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	battery = []
	heapq.heapify(battery)
	power = 0
	i = 0
	t = (n + 1) // 2
	while power < x and i < t:
		if i == n - i - 1:
			temp = [-1, l[i]]
		else:
			temp = sorted([l[i], l[n - i - 1]])
		power += temp[1]
		heapq.heappush(battery, temp[1])
		y = heapq.heappop(battery)
		heapq.heappush(battery, y)
		if temp[0] > y:
			power -= heapq.heappop(battery)
			power += temp[0]
			heapq.heappush(battery, temp[0])
		i += 1
	if power >= x:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	time = (n + 1) // 2
	(energy, flag) = (0, 1)
	temp = []
	for i in range(time):
		elem = max(l[0], l[-1])
		energy += elem
		if len(l) > 1:
			minn = min(l[0], l[-1])
			temp.append(elem)
			val = min(temp)
			if val < minn:
				energy = energy - val + minn
				temp.remove(val)
				temp.append(minn)
		l.pop(0)
		if l:
			l.pop()
		if energy >= x:
			print('YES')
			flag = 0
			break
	if flag:
		print('NO')


import bisect
for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	battery = []
	power = 0
	i = 0
	t = (n + 1) // 2
	while power < x and i < t:
		if i == n - i - 1:
			temp = [-1, l[i]]
		else:
			temp = sorted([l[i], l[n - i - 1]])
		power += temp[1]
		pos = bisect.bisect_right(battery, temp[1], lo=0, hi=len(battery))
		battery.insert(pos, temp[1])
		if temp[0] > battery[0]:
			power -= battery.pop(0)
			power += temp[0]
			pos = bisect.bisect_right(battery, temp[0], lo=0, hi=len(battery))
			battery.insert(pos, temp[0])
		i += 1
	if power >= x:
		print('YES')
	else:
		print('NO')


from math import ceil
import heapq
T = int(input())
ans = []
for _ in range(T):
	(N, X) = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	H = []
	heapq.heapify(H)
	energy = 0
	for i in range(ceil(N / 2) - 1, -1, -1):
		heapq.heappush(H, -A[i])
		if i != N - i - 1:
			heapq.heappush(H, -A[N - i - 1])
		energy += -heapq.heappop(H)
	if energy >= X:
		ans.append('YES')
	else:
		ans.append('NO')
for i in ans:
	print(i)


from heapq import heapify, heappush, heappop
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	l = list(map(int, input().split()))
	time = (n + 1) // 2
	h = []
	heapify(h)
	energy = max(l[0], l[-1])
	heappush(h, energy)
	for i in range(1, time):
		(left, right) = (i, n - 1 - i)
		mx = max(l[left], l[right])
		mn = min(l[left], l[right])
		energy += mx
		heappush(h, mx)
		if left != right:
			if h[0] < mn:
				energy -= h[0]
				heappop(h)
				energy += mn
				heappush(h, mn)
	if energy >= x:
		print('YES')
	else:
		print('NO')


import heapq
for i in range(int(input())):
	(n, x) = list(map(int, input().split()))
	list1 = list(map(int, input().split()))
	if n == 2:
		if max(list1) >= x:
			print('YES')
		else:
			print('NO')
		continue
	i = 1
	j = n - 2
	ans = 0
	flg = 0
	list2 = [max(list1[0], list1[-1])]
	heapq.heapify(list2)
	while j >= i:
		(max1, min1) = (max(list1[i], list1[j]), min(list1[i], list1[j]))
		if i == j:
			heapq.heappush(list2, max1)
			break
		heapq.heappush(list2, max1)
		ele = heapq.heappop(list2)
		heapq.heappush(list2, max(min1, ele))
		i += 1
		j -= 1
	if sum(list(list2)) >= x:
		print('YES')
	else:
		print('NO')


from math import ceil
import heapq
t = int(input())
a = []
for _ in range(t):
	(r, X) = [int(i) for i in input().split()]
	A = [int(i) for i in input().split()]
	u = []
	heapq.heapify(u)
	energy = 0
	for i in range(ceil(r / 2) - 1, -1, -1):
		heapq.heappush(u, -A[i])
		if i != r - i - 1:
			heapq.heappush(u, -A[r - i - 1])
		energy += -heapq.heappop(u)
	if energy >= X:
		a.append('YES')
	else:
		a.append('NO')
for i in a:
	print(i)