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

Source: codechef | Difficulty: MEDIUM
Tags: Data structures


Solutions:
import heapq as heap

def Solve(l, n, k):
	(motu, tomu) = ([], [])
	heap.heapify(motu)
	heap.heapify(tomu)
	(motu_score, tomu_score) = (0, 0)
	for i in range(n):
		if i & 1 == 1:
			tomu_score += l[i]
			heap.heappush(tomu, l[i])
		else:
			motu_score += l[i]
			heap.heappush(motu, -l[i])
	while k != 0:
		if tomu_score > motu_score:
			return 'YES'
		max_motu = -heap.heappop(motu)
		min_tomu = heap.heappop(tomu)
		heap.heappush(motu, -min_tomu)
		heap.heappush(tomu, max_motu)
		tomu_score = tomu_score - min_tomu + max_motu
		motu_score = motu_score - max_motu + min_tomu
		k = k - 1
	if tomu_score > motu_score:
		return 'YES'
	return 'NO'
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	print(Solve(l, n, k))


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


for _ in range(int(input())):
	(length, swap) = (int(x) for x in input().split())
	sequence = [int(x) for x in input().split()]
	motu = []
	tomu = []
	motu_sc = 0
	tomu_sc = 0
	for i in range(0, length, 2):
		motu.append(sequence[i])
		motu_sc += sequence[i]
		if i == length - 1 and (length - 1) % 2 == 0:
			break
		tomu.append(sequence[i + 1])
		tomu_sc += sequence[i + 1]
	if tomu_sc > motu_sc:
		print('YES')
		continue
	elif tomu_sc < motu_sc and swap == 0:
		print('NO')
		continue
	for _ in '.' * swap:
		(tomu[tomu.index(min(tomu))], motu[motu.index(max(motu))]) = (max(motu), min(tomu))
		swap -= 1
		if swap == 0:
			break
	if sum(tomu) > sum(motu):
		print('YES')
	else:
		print('NO')


T = int(input())
for i in range(T):
	(N, K) = tuple(input().split())
	(N, K) = (int(N), int(K))
	A = input().split()
	P = [int(A[j]) for j in range(0, N, 2)]
	Q = [int(A[j]) for j in range(1, N, 2)]
	for i in range(K):
		(a, b) = (max(P), min(Q))
		P.append(b)
		P.remove(a)
		Q.append(a)
		Q.remove(b)
	if sum(Q) > sum(P):
		print('YES')
	else:
		print('NO')


for t in range(int(input())):
	(n, k) = map(int, input().split(' '))
	l = list(map(int, input().split(' ')))
	t = []
	m = []
	for i in range(n):
		if i % 2 == 0:
			m.append(l[i])
		else:
			t.append(l[i])
	for i in range(k):
		max_in_motu = max(m)
		min_in_tomu = min(t)
		maloc = m.index(max_in_motu)
		miloc = t.index(min_in_tomu)
		t[miloc] = max_in_motu
		m[maloc] = min_in_tomu
	if sum(t) > sum(m):
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	xm = [lst[i] for i in range(0, n, 2)]
	xt = [lst[i] for i in range(1, n, 2)]
	for i in range(k):
		mx = max(xm)
		mi = min(xt)
		xm.remove(mx)
		xt.remove(mi)
		xm.append(mi)
		xt.append(mx)
	if sum(xm) < sum(xt):
		print('YES')
	else:
		print('NO')


for i in range(0, int(input())):
	(n, k) = map(int, input().split())
	li = list(map(int, input().split()))
	ms = 0
	ts = 0
	tomu = li[1::2]
	monu = li[::2]
	for i in range(k):
		M = max(monu)
		m = min(tomu)
		if M > m:
			ms += m
			ts += M
			tomu.remove(m)
			monu.remove(M)
	ts += sum(tomu)
	ms += sum(monu)
	print('YES') if ts > ms else print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	lst = list(map(int, input().split()))
	lm = []
	lt = []

	def suml(l):
		t = 0
		for i in l:
			t += i
		return t
	for i in range(n):
		if i % 2 == 0:
			lm.append(lst[i])
		else:
			lt.append(lst[i])
	lt.sort()
	lm.sort(reverse=True)
	for j in range(len(lt)):
		if lt[j] < lm[j] and k > 0:
			flag = lt[j]
			lt[j] = lm[j]
			lm[j] = flag
			k -= 1
	if suml(lt) > suml(lm):
		print('YES')
	else:
		print('NO')


a = int(input(''))
for i in range(a):
	(N, K) = [int(x) for x in input('').split()]
	t = [int(x) for x in input('').split()]
	l1 = [t[i] for i in range(0, N, 2)]
	l2 = [t[j] for j in range(1, N, 2)]
	for h in range(K):
		m1 = max(l1)
		m2 = min(l2)
		l1.remove(m1)
		l2.remove(m2)
		l1.append(m2)
		l2.append(m1)
	if sum(l1) < sum(l2):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = [l[i] for i in range(0, n, 2)]
	l2 = [l[i] for i in range(1, n, 2)]
	if sum(l2) > sum(l1):
		print('YES')
	else:
		l2.sort()
		l1.sort(reverse=True)
		for i in range(min(k, len(l2))):
			(l1[i], l2[i]) = (l2[i], l1[i])
			if sum(l2) > sum(l1):
				print('YES')
				break
		else:
			print('NO')


for _ in range(int(input())):
	(n, swaps) = [int(x) for x in input().split()]
	points = [int(x) for x in input().split()]
	motus = [x for (i, x) in enumerate(points) if not i % 2]
	tomus = [x for (i, x) in enumerate(points) if i % 2]
	motus.sort()
	tomus.sort()
	i = 0
	st = sum(tomus)
	sm = sum(motus)
	while swaps > 0 and st <= sm and (i < len(tomus)):
		st += motus[~i] - tomus[i]
		sm += tomus[i] - motus[~i]
		swaps -= 1
		i += 1
	print('YES' if st > sm else 'NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	(odd, even) = ([], [])
	for i in range(n):
		if i & 1 == 0:
			even.append(arr[i])
		else:
			odd.append(arr[i])
	odd.sort()
	even.sort(reverse=True)
	for i in range(len(odd)):
		if odd[i] < even[i] and k > 0:
			(odd[i], even[i]) = (even[i], odd[i])
			k -= 1
	if sum(odd) > sum(even):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	(motu, tomu) = ([], [])
	for i in range(0, n, 2):
		if i == n - 1:
			motu.append(arr[i])
		else:
			motu.append(arr[i])
			tomu.append(arr[i + 1])
	for i in range(k):
		(high, low) = (max(motu), min(tomu))
		if high > low:
			motu.remove(high)
			motu.append(low)
			tomu.remove(low)
			tomu.append(high)
		else:
			break
	print('YES') if sum(tomu) > sum(motu) else print('NO')


for t in range(int(input())):
	(n, k) = map(int, input().split())
	a = [int(c) for c in input().split()]
	x = []
	y = []
	for i in range(1, n, 2):
		x.append(a[i - 1])
		y.append(a[i])
	try:
		x.append(a[n // 2 * 2])
	except:
		c = 0
	for i in range(k):
		n = x.index(max(x))
		m = y.index(min(y))
		(x[n], y[m]) = (y[m], x[n])
	if sum(x) < sum(y):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(N, K) = map(int, input().split())
	A = list(map(int, input().split()))
	motuScore = [A[i] for i in range(len(A)) if not i % 2]
	tomuScore = [A[i] for i in range(len(A)) if i % 2]
	motuBest = sorted(motuScore, reverse=True)
	tomuWorst = sorted(tomuScore)
	diff = sum([motuBest[i] - tomuWorst[i] for i in range(min(K, len(motuScore), len(tomuScore))) if motuBest[i] - tomuWorst[i] > 0])
	if sum(tomuScore) + diff > sum(motuScore) - diff:
		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')


for i in range(int(input())):
	(a, b) = map(int, input().split())
	x = list(map(int, input().split()))
	A = sorted(x[0::2])
	B = sorted(x[1::2])
	for i in range(min(b, len(A))):
		if i < len(B) and sum(A) > sum(B):
			(A[len(A) - i - 1], B[i]) = (B[i], A[len(A) - i - 1])
	if sum(B) > sum(A):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	(odds, evens) = ([l[i] for i in range(len(l)) if i % 2 != 0], [l[i] for i in range(len(l)) if i % 2 == 0])
	odds.sort()
	evens.sort(reverse=True)
	for i in range(min(len(evens), len(odds), k)):
		if odds[i] < evens[i]:
			(odds[i], evens[i]) = (evens[i], odds[i])
	print('YES' if sum(odds) > sum(evens) else 'NO')


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


for i in range(int(input())):
	(n, k) = map(int, input().split())
	list_games = list(map(int, input().split()))
	if len(set(list_games)) == 1:
		print('NO')
	else:
		list_monu = list_games[::2]
		list_tomu = list_games[1::2]
		if sum(list_monu) < sum(list_tomu):
			print('YES')
		else:
			list_tomu.sort()
			list_monu.sort()
			for j in range(len(list_tomu)):
				if sum(list_monu) > sum(list_tomu) and k > 0:
					(list_monu[len(list_monu) - j - 1], list_tomu[j]) = (list_tomu[j], list_monu[len(list_monu) - j - 1])
					k -= 1
				else:
					break
			if sum(list_monu) < sum(list_tomu):
				print('YES')
			else:
				print('NO')


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l = [int(x) for x in input().split()]
	l1 = l[0::2]
	l2 = l[1::2]
	while k != 0:
		m = l1.index(max(l1))
		n = l2.index(min(l2))
		(l1[m], l2[n]) = (l2[n], l1[m])
		k -= 1
	if sum(l1) < sum(l2):
		print('YES')
	else:
		print('NO')


def sort_inputs(inp1, inp2):
	inp_arr = inp1.split(' ')
	(N, K) = (int(inp_arr[0]), int(inp_arr[1]))
	inp_arr = inp2.split()
	A = list(map(lambda x: int(x), inp_arr))
	return (N, K, A)

def sort_arr(A, N):
	(motu, tomu) = (list(), list())
	for i in range(N):
		if i % 2 == 0:
			motu.append(A[i])
		else:
			tomu.append(A[i])
	motu.sort()
	tomu.sort()
	return (motu, tomu)

def find_k_diff(motu, tomu, K, actual_diff):
	length_tomu = len(tomu)
	length_motu = len(motu)
	if length_motu > length_tomu:
		motu = motu[1:]
		length_motu = len(motu)
	if K >= length_tomu:
		K = length_tomu
	(sum_tomu, sum_motu) = (0, 0)
	for i in range(K):
		sum_tomu = sum_tomu + tomu[i]
		sum_motu = sum_motu + motu[length_motu - 1 - i]
		K_diff = sum_motu - sum_tomu
		if actual_diff < 2 * K_diff:
			return True
	return False

def main_logic(N, K, A):
	(motu, tomu) = sort_arr(A, N)
	actual_diff = sum(motu) - sum(tomu)
	if actual_diff < 0:
		return True
	K_diff = find_k_diff(motu, tomu, K, actual_diff)
	if K_diff:
		return True
	else:
		return False

def main():
	T = int(input())
	for i in range(T):
		inp1 = input()
		inp2 = input()
		(N, K, A) = sort_inputs(inp1, inp2)
		yes_or_no = main_logic(N, K, A)
		if yes_or_no:
			print('YES')
		else:
			print('NO')
main()


T = int(input())
for _ in range(T):
	(N, k) = map(int, input().split())
	l = list(map(int, input().split()))
	m = 0
	t = 0
	mo = sorted(l[0:N:2])
	to = sorted(l[1:N:2])
	k = min(len(to), k)
	for i in range(k):
		if mo[len(mo) - i - 1] > to[i]:
			temp = to[i]
			to[i] = mo[len(mo) - i - 1]
			mo[len(mo) - i - 1] = temp
	m = sum(mo)
	t = sum(to)
	if t > m:
		print('YES')
	else:
		print('NO')


for i in range(int(input())):
	(N, K) = map(int, input().split())
	lst = list(map(int, input().split()))
	odd_lst = []
	even_lst = []
	for i in range(N):
		if i % 2:
			odd_lst.append(lst[i])
		else:
			even_lst.append(lst[i])
	even_lst = sorted(even_lst)[::-1]
	odd_lst = sorted(odd_lst)
	for i in range(min(K, len(even_lst), len(odd_lst))):
		if even_lst[i] > odd_lst[i]:
			(odd_lst[i], even_lst[i]) = (even_lst[i], odd_lst[i])
	if sum(even_lst) >= sum(odd_lst):
		print('NO')
	else:
		print('YES')


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	l1 = []
	l2 = []
	flag = 0
	for i in range(n):
		if i % 2 == 0:
			l1.append(l[i])
		else:
			l2.append(l[i])
	a = sum(l1)
	b = sum(l2)
	if b > a:
		print('YES')
		flag = 1
	else:
		for i in range(k):
			x = max(l1)
			y = min(l2)
			a -= x
			b -= y
			a += y
			b += x
			if b > a:
				print('YES')
				flag = 1
				break
	if flag == 0:
		print('NO')
	t -= 1


t = int(input())
for q in range(t):
	(n, k) = map(int, input().split())
	total = list(map(int, input().split()))
	tomu = []
	motu = []
	for i in range(0, len(total), 2):
		motu.append(total[i])
	for i in range(1, len(total), 2):
		tomu.append(total[i])
	sumT = sum(tomu)
	sumM = sum(motu)
	if sumT > sumM:
		print('YES')
	else:
		motu.sort()
		tomu.sort()
		for c in range(k):
			motu.sort()
			tomu.sort()
			if motu[len(motu) - 1] > tomu[0]:
				t = motu[len(motu) - 1]
				motu[len(motu) - 1] = tomu[0]
				tomu[0] = t
			sumT = sum(tomu)
			sumM = sum(motu)
		if sumT > sumM:
			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')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	A = [int(x) for x in input().split()]
	M = A[::2]
	T = A[1::2]
	for _ in range(k):
		minval = min(T)
		T[T.index(min(T))] = max(M)
		M[M.index(max(M))] = minval
	if sum(T) > sum(M):
		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])
	t = sum(tarr)
	m = sum(marr)
	if t > m:
		print('YES')
	else:
		print('NO')


q = int(input())
for i in range(q):
	w = str(input())
	w = w + ' '
	e = ''
	r = []
	for i in w:
		if i == ' ':
			r.append(int(e))
			e = ''
		else:
			e = e + i
	t = str(input())
	t = t + ' '
	y = ''
	u = []
	for i in t:
		if i == ' ':
			u.append(int(y))
			y = ''
		else:
			y = y + i
	o = []
	for i in range(0, len(u), 2):
		o.append(u[i])
	p = []
	for i in range(1, len(u), 2):
		p.append(u[i])
	o.sort()
	p.sort()
	if sum(o) < sum(p):
		print('YES')
	else:
		s = 0
		if len(p) >= r[1]:
			for i in range(r[1]):
				a = o[-(i + 1)]
				o[-(i + 1)] = p[i]
				p[i] = a
				if sum(o) < sum(p):
					print('YES')
					break
				else:
					s = s + 1
			if s == r[1]:
				print('NO')
		if len(p) < r[1]:
			for i in range(len(p)):
				a = o[-(i + 1)]
				o[-(i + 1)] = p[i]
				p[i] = a
				if sum(o) < sum(p):
					print('YES')
					break
				else:
					s = s + 1
			if s == len(p):
				print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	odd = []
	even = []
	for i in range(n):
		if i % 2:
			odd.append(l[i])
		else:
			even.append(l[i])
	even = sorted(even)[::-1]
	odd = sorted(odd)
	for i in range(min(k, len(even), len(odd))):
		if even[i] > odd[i]:
			(odd[i], even[i]) = (even[i], odd[i])
	if sum(even) >= sum(odd):
		print('NO')
	else:
		print('YES')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	fr = list(map(int, input().split()))
	to = []
	mo = []
	for i in range(n):
		if i % 2 != 0:
			to.append(fr[i])
		else:
			mo.append(fr[i])
	to.sort()
	mo.sort(reverse=True)
	for i in range(len(to)):
		if to[i] < mo[i] and k > 0:
			(to[i], mo[i]) = (mo[i], to[i])
			k -= 1
	if sum(to) > sum(mo):
		print('YES')
	else:
		print('NO')


def f(l, n, k):
	k = min(n // 2, k)
	a = sorted([l[i] for i in range(0, n, 2)], reverse=True)
	b = sorted([l[i] for i in range(1, n, 2)])
	t = 0
	for i in range(k):
		if a[i] > b[i]:
			(a[i], b[i]) = (b[i], a[i])
		else:
			break
	return 'YES' if sum(b) > sum(a) else 'NO'
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	print(f([int(i) for i in input().split()], n, k))


for t in range(int(input())):
	(n, k) = map(int, input().split(' '))
	a = list(map(int, input().split(' ')))
	m = [a[j] for j in range(0, n, 2)]
	t = [a[j] for j in range(1, n, 2)]
	for i in range(k):
		(m[m.index(max(m))], t[t.index(min(t))]) = (min(t), max(m))
	if sum(t) > sum(m):
		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
	if sum(tomu) > sum(motu):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	n_k = input().split(' ')
	(n, k) = (int(n_k[0]), int(n_k[1]))
	arr = input().split(' ')
	(l_m, l_t) = ([], [])
	for j in range(n):
		if j % 2 == 0:
			l_m.append(int(arr[j]))
		else:
			l_t.append(int(arr[j]))
	if sum(l_t) > sum(l_m):
		print('YES')
	elif sum(l_t) <= sum(l_m) and k == 0:
		print('NO')
	else:
		l_t.sort()
		l_m.sort()
		for x in range(k):
			if l_t[0] < l_m[-1]:
				(l_t[0], l_m[-1]) = (l_m[-1], l_t[0])
				l_t.sort()
				l_m.sort()
			else:
				break
		if sum(l_t) > sum(l_m):
			print('YES')
		else:
			print('NO')


T = int(input())
for i in range(T):
	(N, K) = map(int, input().split())
	A = list(input().split())
	a = list(map(int, A))
	Motu_score = 0
	Tomu_score = 0
	Tomu_list = a[1::2]
	Motu_list = a[::2]
	for i in range(K):
		M = max(Motu_list)
		m = min(Tomu_list)
		if M > m:
			Tomu_score += M
			Motu_score += m
			Motu_list.remove(M)
			Tomu_list.remove(m)
	Motu_score += sum(Motu_list)
	Tomu_score += sum(Tomu_list)
	if Motu_score >= Tomu_score:
		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 i in range(int(input())):
	(x, k) = map(int, input().split())
	y = list(map(int, input().split()))
	a = []
	b = []
	for i in range(x):
		if i % 2:
			b.append(y[i])
		else:
			a.append(y[i])
	a.sort(reverse=1)
	b.sort()
	s1 = sum(a)
	s2 = sum(b)
	if s2 > s1:
		print('YES')
	else:
		for i in range(min(k, len(a), len(b))):
			s1 = s1 + b[i] - a[i]
			s2 = s2 + a[i] - b[i]
			if s2 > s1:
				print('YES')
				break
		else:
			print('NO')


tc = int(input())
for _ in range(tc):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	odd = []
	even = []
	for i in range(0, n - 1, 2):
		odd.append(a[i])
		even.append(a[i + 1])
	if n % 2 == 1:
		odd.append(a[n - 1])
	gorb = False
	if sum(even) > sum(odd):
		gorb = True
	else:
		for i in range(k):
			ma = max(odd)
			odd.remove(ma)
			mi = min(even)
			even.remove(mi)
			odd.append(mi)
			even.append(ma)
			if sum(even) > sum(odd):
				gorb = True
				break
	print('YES' if gorb else 'NO')


for i in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	(a1, b1) = ([], [])
	alternate = True
	for j in a:
		if alternate:
			a1.append(j)
			alternate = False
		else:
			b1.append(j)
			alternate = True
	s1 = sum(a1)
	s2 = sum(b1)
	if s1 < s2:
		print('YES')
	else:
		a1.sort(reverse=True)
		b1.sort()
		for j in range(0, n // 2):
			if k:
				k -= 1
				if a1[j] >= b1[j]:
					s1 = s1 - a1[j] + b1[j]
					s2 = s2 - b1[j] + a1[j]
					(a1[j], b1[j]) = (b1[j], a1[j])
				else:
					break
		if s1 < s2:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	s = 0
	(m, p) = ([], [])
	for i in input().split():
		if s % 2 == 0:
			m.append(int(i))
		else:
			p.append(int(i))
		s += 1
	m.sort(reverse=True)
	p.sort()
	if k > min(len(m), len(p)):
		k = min(len(m), len(p))
	for i in range(k):
		if m[i] > p[i]:
			(m[i], p[i]) = (p[i], m[i])
	if sum(p) > sum(m):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	m = [a[i] for i in range(len(a)) if i % 2 == 0]
	t = [a[i] for i in range(len(a)) if i % 2 != 0]
	ms = sum(m)
	ts = sum(t)
	if ms >= ts:
		for i in range(k):
			maxm = max(m)
			mint = min(t)
			mindex = m.index(maxm)
			tindex = t.index(mint)
			(m[mindex], t[tindex]) = (t[tindex], m[mindex])
		if sum(m) >= sum(t):
			print('NO')
		else:
			print('YES')
	else:
		print('YES')


for tc in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	motu = []
	tomu = []
	for i in range(n):
		if i % 2 == 0:
			motu.append(a[i])
		else:
			tomu.append(a[i])
	motu.sort(reverse=True)
	tomu.sort()
	for i in range(len(tomu)):
		if tomu[i] < motu[i] and k > 0:
			(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) = [int(x) for x in input().split()]
	lst = [int(x) for x in input().split()]
	l1 = []
	l2 = []
	for i in range(0, n, 2):
		l1.append(lst[i])
	for i in range(1, n, 2):
		l2.append(lst[i])
	l1.sort(reverse=True)
	l2.sort()
	tmp = 0
	for i in range(k):
		if l1[i] > l2[i] and i < n // 2:
			tmp = l2[i]
			l2[i] = l1[i]
			l1[i] = tmp
		else:
			break
	if sum(l2) > sum(l1):
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	(n, k) = list(map(int, input().split()))
	l = list(map(int, input().split()))
	motu = []
	tomu = []
	for i in range(n):
		if i % 2 == 0:
			motu.append(l[i])
		else:
			tomu.append(l[i])
	for i in range(k):
		mx = max(motu)
		mn = min(tomu)
		motu.remove(mx)
		tomu.remove(mn)
		motu.append(mn)
		tomu.append(mx)
	cmot = 0
	ctom = 0
	for i in range(len(motu)):
		cmot += motu[i]
	for i in range(len(tomu)):
		ctom += tomu[i]
	if ctom > cmot:
		print('YES')
	else:
		print('NO')
	t -= 1


from math import sqrt, ceil, floor, gcd, log2
import sys
from sys import stdin, stdout
from collections import Counter, defaultdict, OrderedDict, deque
from itertools import combinations, groupby
from time import time
from heapq import heappop, heappush, heapify
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	(m, t) = ([], [])
	for i in range(n):
		if i % 2:
			t.append(arr[i])
		else:
			m.append(arr[i])
	if sum(t) > sum(m):
		print('YES')
	else:
		m.sort(reverse=True)
		t.sort()
		s = sum(t)
		ms = sum(m)
		i = 0
		flag = 0
		while k:
			if i < len(t) and i < len(m):
				s -= t[i]
				s += m[i]
				ms -= m[i]
				ms += t[i]
				if s > ms:
					print('YES')
					flag = 1
					break
			i += 1
			k -= 1
		if not flag:
			print('NO')


for tc in range(int(input())):
	(m, t) = ([], [])
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	for i in range(n):
		if i % 2 == 0:
			m.append(arr[i])
		else:
			t.append(arr[i])
	m.sort(reverse=True)
	t.sort()
	totdiff = 0
	for i in range(min(k, n // 2)):
		if m[i] > t[i]:
			totdiff += m[i] - t[i]
		else:
			break
	ms = sum(m)
	ts = sum(t)
	if ms - totdiff < ts + totdiff:
		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')


t = int(input())
for i in range(t):
	(n, k) = input().split()
	n = int(n)
	k = int(k)
	A = [int(x) for x in input().split()]
	B = []
	b = 0
	c = 0
	C = []
	for j in range(n):
		if j % 2 == 0:
			B.append(A[j])
			b += A[j]
		else:
			C.append(A[j])
			c += A[j]
	B.sort()
	C.sort()
	ans = 0
	if c > b:
		print('YES')
	else:
		for j in range(min(len(C), k)):
			b = b - B[len(B) - j - 1] + C[j]
			c = c + B[len(B) - j - 1] - C[j]
			if c > b:
				ans = 1
				break
		if ans == 1:
			print('YES')
		else:
			print('NO')


for i in range(int(input())):
	(s, k) = map(int, input().split())
	l = list(map(int, input().split()))
	c = sum(l[::2])
	d = sum(l[1::2])
	if k == 0:
		if c < d:
			print('YES')
		else:
			print('NO')
	else:
		l1 = l[::2]
		l2 = l[1::2]
		while k >= 1:
			if max(l1) > min(l2):
				l2.append(max(l1))
				l1.append(min(l2))
				l2.remove(min(l2))
				l1.remove(max(l1))
			else:
				break
			k = k - 1
		f = sum(l1)
		g = sum(l2)
		if g > f:
			print('YES')
		else:
			print('NO')


for _ in range(int(input())):
	(n, S) = [int(x) for x in input().split()]
	P = [int(x) for x in input().split()]
	M = [x for (i, x) in enumerate(P) if not i % 2]
	T = [x for (i, x) in enumerate(P) if i % 2]
	M.sort()
	T.sort()
	i = 0
	st = sum(T)
	sm = sum(M)
	while S > 0 and st <= sm and (i < len(T)):
		st += M[~i] - T[i]
		sm += T[i] - M[~i]
		S -= 1
		i += 1
	print('YES' if st > sm else 'NO')


from math import fsum
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	nums = list(map(int, input().split()))
	(mot, tom) = ([], [])
	for (i, val) in enumerate(nums):
		if i % 2 == 0:
			mot.append(val)
		else:
			tom.append(val)
	tom.sort()
	mot.sort()
	mot_score1 = fsum(mot)
	tom_score1 = fsum(tom)
	diff = tom_score1 - mot_score1
	if diff > 0:
		print('YES')
		continue
	diff = abs(diff)
	if k == 0:
		print('NO')
		continue
	nada = False
	for i in range(len(tom)):
		if i == k:
			nada = True
			break
		t = tom[i]
		m = mot[len(mot) - 1 - i]
		if t < m:
			d = m - t
			tom_score1 += d
			mot_score1 -= d
			if tom_score1 > mot_score1:
				print('YES')
				break
	else:
		print('NO')
	if nada == True:
		print('NO')


def func():
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	m = []
	t = []
	for i in range(1, n, 2):
		m.append(arr[i - 1])
		t.append(arr[i])
	if n % 2 != 0:
		m.append(arr[n - 1])
	while k > 0:
		if sum(t) > sum(m):
			break
		h = max(m)
		l = min(t)
		if l >= h:
			break
		m[m.index(h)] = l
		t[t.index(l)] = h
		k -= 1
	if sum(t) > sum(m):
		print('YES')
	else:
		print('NO')
for i in range(int(input())):
	func()


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


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = list(map(int, input().split()))
	b = []
	c = []
	for i in range(0, n):
		if i % 2 == 0:
			b.append(a[i])
		else:
			c.append(a[i])
	for i in range(x):
		k = max(b)
		l = min(c)
		b.remove(k)
		c.append(k)
		b.append(l)
		c.remove(l)
	if sum(c) > sum(b):
		print('YES')
	else:
		print('NO')


z = int(input())
while z:
	z -= 1
	(a, b) = map(int, input().split())
	l = list(map(int, input().split()))
	(m, t) = ([], [])
	for i in range(0, a):
		if i % 2 == 0:
			m.append(l[i])
		else:
			t.append(l[i])
	m = sorted(m)
	t = sorted(t)
	while b:
		b -= 1
		h = m.pop(-1)
		k = t.pop(0)
		if h > k:
			t.append(h)
			m.insert(0, k)
		else:
			t.append(k)
			m.insert(0, h)
	if sum(t) > sum(m):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	l = list(map(int, input().split()))
	p = l[:n:2]
	q = l[1:n:2]
	p.sort(reverse=True)
	q.sort()
	for i in range(k):
		if p[i] <= q[i]:
			break
		(p[i], q[i]) = (q[i], p[i])
	if sum(q) > sum(p):
		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')


for test in range(int(input())):
	(num, kum) = map(int, input().split())
	aum = list(map(int, input().split()))
	mum = [aum[i] for i in range(num) if i % 2 == 0]
	tum = [aum[i] for i in range(num) if i % 2 != 0]
	for i in range(kum):
		tum.sort()
		mum.sort(reverse=True)
		(mum[0], tum[0]) = (tum[0], mum[0])
	if sum(tum) > sum(mum):
		print('YES')
	else:
		print('NO')


import heapq
t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	arr = list(map(int, input().split()))
	tom = []
	motu = []
	t_s = 0
	m_s = 0
	heapq.heapify(motu)
	heapq.heapify(tom)
	for i in range(n):
		if i & 1 == 1:
			heapq.heappush(tom, arr[i])
			t_s += arr[i]
		else:
			heapq.heappush(motu, -arr[i])
			m_s += arr[i]
	flag = 0
	while k != 0:
		k -= 1
		if t_s > m_s:
			flag = 1
			break
		m_max = -heapq.heappop(motu)
		t_min = heapq.heappop(tom)
		heapq.heappush(motu, -t_min)
		heapq.heappush(tom, m_max)
		m_s = m_s + t_min - m_max
		t_s = t_s + m_max - t_min
	if t_s > m_s:
		flag = 1
	if flag == 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for t in range(t):
	(n, k) = [int(i) for i in input().split()]
	arr = [int(i) for i in input().split()]
	(m, t) = ([], [])
	i = 0
	j = 1
	while i < n:
		if n % 2 == 0:
			m.append(arr[i])
			t.append(arr[j])
		else:
			m.append(arr[i])
			if j < n - 1:
				t.append(arr[j])
		i += 2
		j += 2
	m = sorted(m, reverse=True)
	t = sorted(t)
	for i in range(len(t)):
		if m[i] > t[i] and k > 0:
			(m[i], t[i]) = (t[i], m[i])
			k -= 1
	sum_m = sum(m)
	sum_t = sum(t)
	if sum_t > sum_m:
		print('YES')
	else:
		print('NO')


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


t = int(input())
while t:
	(n, k) = map(int, input().split(' '))
	list1 = list(map(int, input().split(' ')))
	motu = []
	tomu = []
	for i in range(0, n, 2):
		motu.append(list1[i])
	for i in range(1, n, 2):
		tomu.append(list1[i])
	motu.sort(reverse=True)
	tomu.sort(reverse=True)
	motusum = sum((i for i in motu))
	tomusum = sum((i for i in tomu))
	motulen = len(motu)
	tomulen = len(tomu)
	if tomusum > motusum:
		print('YES')
		t = t - 1
		continue
	else:
		if k > n / 2:
			k = int(n / 2)
		for i in range(k):
			if tomu[-1 - i] < motu[i]:
				a = motu[i]
				motu[i] = tomu[-1 - i]
				tomu[-1 - i] = a
	motusum = sum((i for i in motu))
	tomusum = sum((i for i in tomu))
	if tomusum > motusum:
		print('YES')
	else:
		print('NO')
	t = t - 1