Motu and Tomu are very good friends who are always looking for new games to play against each other and ways to win these games. One day, they decided to play a new type of game with the following rules:
- The game is played on a sequence $A_0, A_1, \dots, A_{N-1}$.
- The players alternate turns; Motu plays first, since he's earlier in lexicographical order.
- Each player has a score. The initial scores of both players are $0$.
- On his turn, the current player has to pick the element of $A$ with the lowest index, add its value to his score and delete that element from the sequence $A$.
- At the end of the game (when $A$ is empty), Tomu wins if he has strictly greater score than Motu. Otherwise, Motu wins the game.
In other words, Motu starts by selecting $A_0$, adding it to his score and then deleting it; then, Tomu selects $A_1$, adds its value to his score and deletes it, and so on.
Motu and Tomu already chose a sequence $A$ for this game. However, since Tomu plays second, he is given a different advantage: before the game, he is allowed to perform at most $K$ swaps in $A$; afterwards, the two friends are going to play the game on this modified sequence.
Now, Tomu wants you to determine if it is possible to perform up to $K$ swaps in such a way that he can win this game.

-----Input-----
- The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
- The first line of each test case contains two space-separated integers $N$ and $K$ denoting the number of elements in the sequence and the maximum number of swaps Tomu can perform.
- The second line contains $N$ space-separated integers $A_0, A_1, \dots, A_{N-1}$.

-----Output-----
For each test case, print a single line containing the string "YES" if Tomu can win the game or "NO" otherwise (without quotes).

-----Constraints-----
- $1 \le T \le 100$
- $1 \le N \le 10,000$
- $0 \le K \le 10,000$
- $1 \le A_i \le 10,000$ for each valid $i$

-----Subtasks-----
Subtask #1 (20 points): $1 \le N \le 100$
Subtask #2 (80 points): original constraints

-----Example Input-----
2
6 0
1 1 1 1 1 1
5 1
2 4 6 3 4

-----Example Output-----
NO
YES

-----Explanation-----
Example case 1: At the end of the game, both Motu and Tomu will have scores $1+1+1 = 3$. Tomu is unable to win that game, so the output is "NO".
Example case 2: If no swaps were performed, Motu's score would be $2+6+4 = 12$ and Tomu's score would be $4+3 = 7$. However, Tomu can swap the elements $A_2 = 6$ and $A_3 = 3$, which makes Motu's score at the end of the game equal to $2+3+4 = 9$ and Tomu's score equal to $4+6 = 10$. Tomu managed to score higher than Motu, so the output is "YES".

Difficulty: interview

Starter code:

Solutions:
for _ in range(int(input())):
 n, k = map(int, input().split())
 arr= list(map(int, input().split()))
 motu, tomu = [], []
 for i in range(n):
  if i%2 == 0:
   motu.append(arr[i])
  else:
   tomu.append((arr[i]))
 motu.sort(reverse=True)
 tomu.sort()
 for i in range(len(motu)):
  if len(tomu)-1<i:
   break
  if k==0:
   break
  if tomu[i]<motu[i]:
   tomu[i], motu[i] = motu[i], tomu[i]
   k-=1
 if sum(tomu) > sum(motu):
  print("YES")
 else:
  print("NO")

T = int(input())
for _ in range(T):
 n, k = list(map(int, input().split()))
 seq = list(map(int, input().split()))
 motu, tomu = [], []
 for i in range(n):
  if i%2 == 0:
   motu.append(seq[i])
  else:
   tomu.append((seq[i]))
 motu.sort(reverse=True)
 tomu.sort()
 for i in range(len(motu)):
  if len(tomu)-1<i:
   break
  if k==0:
   break
  if tomu[i]<motu[i]:
   tomu[i], motu[i] = motu[i], tomu[i]
   k-=1
 # for i in range(k):
 #     if motu[i] > tomu[i]:
 #         motu[i], tomu[i] = tomu[i], motu[i]
 if sum(tomu) > sum(motu):
  print("YES")
 else:
  print("NO")


for _ in range(int(input())):
 n,k=list(map(int,input().split()))
 arr=[int(k) for k in input().split()]
 motu=[]
 tomu=[]
 for i in range(n):
  if i%2==0:
   motu.append(arr[i])
  else:
   tomu.append(arr[i])
 motu.sort(reverse=True)
 tomu.sort()
 for i in range(len(motu)):
  if len(tomu)-1<i:
   break
  if k==0:
   break
  if tomu[i]<motu[i]:
   temp=tomu[i]
   tomu[i]=motu[i]
   motu[i]=temp
   k-=1
 sumtomu=0
 summotu=0
 for i in range(len(tomu)):
  sumtomu+=tomu[i]
 for i in range(len(motu)):
  summotu+=motu[i]
 if sumtomu>summotu:
  print("YES")
 else:
  print("NO")
  
  
   
  


t=int(input())
for _ in range(t):
 n,k=list(map(int,input().split()))
 l=list(map(int,input().split()))
 a=l[0::2]
 b=l[1::2]
 al=len(a)
 bl=len(b)
 if(al>bl):
  ll=bl
 else:
  ll=al
 b.sort()
 a.sort(reverse=True)
 i=0
 while(sum(a)>sum(b) and k>0 and i<ll):
  t=a[i]
  a[i]=b[i]
  b[i]=t
  i=i+1
  k=k-1
 if(sum(b)>sum(a)):
  print('YES')
 else:
  print('NO')


# cook your dish here
import math
t=int(input())
for i in range (t):
 n,k=map(int,input().strip().split(" "))
 a=[int(x) for x in input().split()]
 od_a=[]
 ev_a=[]
 for j in range(n):
  if(j%2==0):
   ev_a.append(a[j])
  else:
   od_a.append(a[j])
 ev_a.sort()
 od_a.sort()
 n1=len(ev_a)
 n2=len(od_a)
 s1=sum(ev_a)
 s2=sum(od_a)
 if(s2>s1):
  print("YES")
  continue
 elif(k==0):
  print("NO")
  continue
 for j in range(k):
  if(j==n2):
   break
  if(ev_a[n1-1-j]>od_a[j]):
   temp=ev_a[n1-1-j]
   ev_a[n1-1-j]=od_a[j]
   od_a[j]=temp
  s1-=(od_a[j]-ev_a[n1-1-j])
  s2+=(od_a[j]-ev_a[n1-1-j]) 
  if(s2>s1):
   print("YES")
   break
 if(s1>=s2):
  print("NO")

# cook your dish here
import math
t=int(input())
for i in range (t):
 n,k=map(int,input().strip().split(" "))
 a=[int(x) for x in input().split()]
 od_a=[]
 ev_a=[]
 for j in range(n):
  if(j%2==0):
   ev_a.append(a[j])
  else:
   od_a.append(a[j])
 ev_a.sort()
 od_a.sort()
 n1=len(ev_a)
 s1=sum(ev_a)
 s2=sum(od_a)
 if(s2>s1):
  print("YES")
  continue
 elif(k==0):
  print("NO")
  continue
 for j in range(k):
  if(j==int(n/2)):
   break
  if(ev_a[n1-1-j]>od_a[j]):
   temp=ev_a[n1-1-j]
   ev_a[n1-1-j]=od_a[j]
   od_a[j]=temp
  s1-=(od_a[j]-ev_a[n1-1-j])
  s2+=(od_a[j]-ev_a[n1-1-j]) 
  if(s2>s1):
   print("YES")
   break
 if(s1>=s2):
  print("NO")

t=int(input())
for _ in range(t):
 n,k=list(map(int,input().split()))
 l=list(map(int,input().split()))
 a=l[0::2]
 b=l[1::2]
 al=len(a)
 bl=len(b)
 if(al>bl):
  ll=bl
 else:
  ll=al
 b.sort()
 a.sort(reverse=True)
 i=0
 while(sum(a)>sum(b) and k>0 and i<ll):
  t=a[i]
  a[i]=b[i]
  b[i]=t
  i=i+1
  k=k-1
 if(sum(b)>sum(a)):
  print('YES')
 else:
  print('NO')
  
 


# cook your dish here
for _ in range(int(input())):
 n,k=map(int,input().split())
 l=list(map(int,input().split()))
 m=[]
 t=[]
 ms=ts=0
 for i in range(n):
  if (i%2)==0:
   m.append(l[i])
  else:
   t.append(l[i])
 ms=sum(m)
 ts=sum(t)
 if ts>ms:
  print('YES')
 else:
  flag=1
  while k>0:
   mm=max(m)
   mn=min(t)
   ts=ts+mm-mn
   ms=ms-mm+mn
   if ts>ms:
    flag=0
    print('YES')
    break
   k-=1
  if flag==1:
   print('NO')

import math
test=int(input())
for j in range(test):
 a=[int(x) for x in input().split()]
 inputdata=[int(x) for x in input().split()]
 new1=[]
 new2=[]
 count=0
 count1=0
 for i in range(a[0]):
  if i%2==0:
   new1.append(inputdata[i]) 
  else: 
   new2.append(inputdata[i])
 count=sum(new1)
 count1=sum(new2)
 new1.sort(reverse=True)
 new2.sort()
 if count<count1:
  print("YES")
 else:
  for i in range(len(new2)):
   if new1[i]>new2[i] and a[1]:
    temp=new1[i]
    new1[i]=new2[i]
    new2[i]=temp 
    a[1]=a[1]-1
   if a[1] is 0:
    break;            
  count=sum(new1)
  count1=sum(new2)
  if count<count1:
   print("YES")
  else: print("NO")

import math
test=int(input())
for j in range(test):
 a=[int(x) for x in input().split()]
 inputdata=[int(x) for x in input().split()]
 new1=[]
 new2=[]
 count=0
 count1=0
 for i in range(a[0]):
  if i%2==0:
   new1.append(inputdata[i]) 
  else: 
   new2.append(inputdata[i])
 count=sum(new1)
 count1=sum(new2)
 new1.sort(reverse=True)
 new2.sort()
 if count<count1:
  print("YES")
 else:
  for i in range(len(new2)):
   if new1[i]>new2[i] and a[1]:
    temp=new1[i]
    new1[i]=new2[i]
    new2[i]=temp 
    a[1]=a[1]-1
   if a[1] is 0:
    break;            
  count=sum(new1)
  count1=sum(new2)
  if count<count1:
   print("YES")
  else: print("NO")

import math
test=int(input())
for j in range(test):
 a=[int(x) for x in input().split()]
 inputdata=[int(x) for x in input().split()]
 new1=[]
 new2=[]
 count=0
 count1=0
 for i in range(a[0]):
  if i%2==0:
   new1.append(inputdata[i]) 
  else: 
   new2.append(inputdata[i])
 count=sum(new1)
 count1=sum(new2)
 new1.sort(reverse=True)
 new2.sort()
 if count<count1:
  print("YES")
 else:
  for i in range(len(new2)):
   if new1[i]>new2[i] and a[1]:
    temp=new1[i]
    new1[i]=new2[i]
    new2[i]=temp 
    a[1]=a[1]-1
   if a[1] is 0:
    break;            
  count=sum(new1)
  count1=sum(new2)
  if count<count1:
   print("YES")
  else: print("NO")

test=int(input())
for x in range(test):
 n,k = list(map(int, input().split()))
 a=list(map(int, input().split()))
 
 tonu=[]
 monu=[]
 
 for i in range(n):
  if ((i+1)%2==0):
   tonu.append(a[i])
  else:
   monu.append(a[i])
 
 tonu.sort()
 monu.sort(reverse= True)
 
 for i in range(k):
  if (sum(tonu)>sum(monu) or (i==len(tonu) or i==len(monu))):
   break
  tonu[i],monu[i]=monu[i],tonu[i]
 
 if sum(tonu)>sum(monu):
  print("YES")
 else:
  print("NO")


t = int(input())

for x in range(t):

 n, k = list(map(int, input().split()))
 a = list(map(int, input().split()))

 tarr = []
 marr = []
 for i in range(n):
  if((i + 1)%2 == 0):
   tarr.append(a[i])
  else:
   marr.append(a[i])

 tarr.sort()
 marr.sort(reverse = True)

 for i in range(k):
  if(sum(tarr) > sum(marr) or (i == len(tarr) or i == len(marr))):
   break
  tarr[i], marr[i] = marr[i], tarr[i]

 #print(tarr, marr)

 t = sum(tarr)
 m = sum(marr)

 if(t > m):
  print('YES')
 else:
  print('NO')

t=int(input())
for i in range(t):
 nk=list(map(int,input().split()))
 n=nk[0]
 k=nk[1]
 arr=list(map(int,input().split()))
 a1=[]
 a2=[]
 for i in range(0,len(arr)):
  if i%2==0:
   a1.append(arr[i])
  else:
   a2.append(arr[i])
 if( sum(a1)>=sum(a2)):
  a1.sort()
  a2.sort()
  for j in range(k):
   if j<len(a1) and j<len(a2):
    temp=a1[len(a1)-j-1]
    a1[len(a1)-j-1]=a2[j]
    a2[j]=temp
 if( sum(a1)>=sum(a2)):
  print("NO")
 else:
  print("YES")

from math import *
T=int(input())
for i in range(T):
 N,K=[int(j) for j in input().split(" ")]
 A=list(map(int,input().split(" ")))
 Ao=[]
 Ae=[]
 for k in range(len(A)):
  if k%2==0:
   Ae.append(A[k])
  else:
   Ao.append(A[k]) 

 count1=0
 count2=0 
 if K==0:
  for r in range(len(A)):
   if r%2==0:      
    count1+=A[r]
   else:
    count2+=A[r] 
 else:
  for o in range(K):
   e=max(Ae)
   f=min(Ao)
   g=Ae.index(e)
   h=Ao.index(f)
   Ae[g]=f
   Ao[h]=e
  for p in range(len(Ae)):
   count1+=Ae[p]
  for w in range(len(Ao)):
   count2+=Ao[w] 
 if count2>count1:
  print("YES")
 else:
  print("NO")


for _ in range(int(input())):
 n,k = list(map(int,input().split()))
 a = list(map(int,input().split()))
 m = []
 t = []
 for i in range(n):
  if(i%2 == 0):
   m.append(a[i])
  else:
   t.append(a[i])
 m.sort(reverse=True)
 t.sort()
 mi=min(len(m),len(t))
 x1=0
 x2=0
 while(k!=0 and x1<len(m) and x2<len(m)):
  if(m[x1]>t[x2]):
   m[x1],t[x2] = t[x2],m[x1]
   x1+=1
   x2+=1
  else:
   break
  k-=1
 if(sum(t) > sum(m)):
  print("YES")
 else:
  print("NO")