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: interview

Starter code:

Solutions:
# cook your dish here
import bisect
for _ in range(int(input())):
 
 n,x=list(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')


# cook your dish here
import bisect
for _ in range(int(input())):
 
 n,x=list(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')


# cook your dish here
import heapq
for _ in range(int(input())):
 
 n,x=list(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')


# cook your dish here
import heapq
for _ in range(int(input())):
 
 n,x=list(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')


# cook your dish here
import heapq
for _ in range(int(input())):
 
 n,x=list(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')


# cook your dish here
import heapq
for _ in range(int(input())):
 
 n,x=list(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')


# cook your dish here
import heapq
for _ in range(int(input())):
 
 n,x=list(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')


# cook your dish here
import heapq
for _ in range(int(input())):
 
 n,x=list(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')


# cook your dish here
import heapq
for _ in range(int(input())):
 
 n,x=list(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')


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")

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")

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")

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")# cook your dish here