To destroy humanity, The Monster Association sent $n$ monsters to Earth's surface. The $i$-th monster has health $h_i$ and power $p_i$.

With his last resort attack, True Spiral Incineration Cannon, Genos can deal $k$ damage to all monsters alive. In other words, Genos can reduce the health of all monsters by $k$ (if $k > 0$) with a single attack.

However, after every attack Genos makes, the monsters advance. With their combined efforts, they reduce Genos' attack damage by the power of the $^\dagger$weakest monster $^\ddagger$alive. In other words, the minimum $p_i$ among all currently living monsters is subtracted from the value of $k$ after each attack.

$^\dagger$The Weakest monster is the one with the least power.

$^\ddagger$A monster is alive if its health is strictly greater than $0$.

Will Genos be successful in killing all the monsters?


-----Input-----

The first line of the input contains a single integer $t$ ($1 \le t \le 100$) — the number of test cases. The description of test cases follows.

The first line of each test case contains two integers, $n$ and $k$ ($1 \le n, k \le 10^5$) — the number of monsters and Genos' initial attack damage. Then two lines follow, each containing $n$ integers describing the arrays $h$ and $p$ ($1 \le h_i, p_i \le 10^9$).

It's guaranteed that the sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.


-----Output-----

For each test case, print the answer — "YES" (without quotes) if Genos could kill all monsters and "NO" otherwise.


-----Examples-----

Input
3
6 7
18 5 13 9 10 1
2 7 2 1 2 6
3 4
5 5 5
4 4 4
3 2
2 1 3
1 1 1
Output
YES
NO
YES


-----Note-----

In the first example, after Genos' first attack, $h$ and $k$ will update to:

$h: [11,0,6,2,3,0]$

$k: 7-1 = 6$

After second attack:

$h: [5,0,0,0,0,0]$

$k: 6-2 = 4$

After third attack:

$h: [1,0,0,0,0,0]$

$k: 4-2 = 2$

After fourth attack:

$h: [0,0,0,0,0,0]$

As Genos could kill all monsters, the answer is YES.

Source: codeforces | Difficulty: EASY
Tags: Sorting

Implementation

Complete search

Mathematics

Data structures


Solutions:
import sys
input = sys.stdin.readline
import math

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

def readInt():
	return int(input())

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

def readStr():
	return input().strip()

def solve():
	(n, k) = readInts()
	H = readList()
	P = readList()
	arr = sorted([[P[i], H[i]] for i in range(n)])
	offset = 0
	for i in range(n):
		(p, h) = arr[i]
		h -= offset
		if h <= 0:
			continue
		k -= p if i > 0 else 0
		if k >= h:
			offset += k
			continue
		elif k <= 0:
			return 'NO'
		D = (p + 2 * k) ** 2 - 8 * p * h
		if D < 0:
			return 'NO'
		x1 = math.ceil((p + 2 * k - D ** 0.5) / (2 * p))
		if x1 > 0 and p * x1 ** 2 - x1 * (p + 2 * k) + 2 * h <= 0:
			offset += k * x1 - p * (x1 - 1) * x1 // 2
			k -= p * (x1 - 1)
		else:
			return 'NO'
	return 'YES'
for _ in range(int(input())):
	print(solve())


import heapq
import math
eps = 10 ** (-9)

def solve():
	(n, k) = input().split(' ')
	(n, k) = (int(n), int(k))
	h = input().split()
	p = input().split()
	a = [(int(p[i]), int(h[i])) for i in range(n)]
	a.sort()
	i = 0
	lost = 0
	while i < n:
		(p, h) = a[i]
		h -= lost
		if h <= 0:
			i += 1
			continue
		if i > 0:
			k -= p
		if k <= 0:
			break
		sq = (1 + 2 * k / p) ** 2 - 4 * 2 * h / p
		b = 1 + 2 * k / p
		if sq < 0:
			print('NO')
			return
		x = math.ceil((b - math.sqrt(sq)) / 2)
		if x < 0:
			x = math.floor((b + math.sqrt(sq)) / 2)
			if x < 0:
				print('NO')
				return
		lost += k * x - x * (x - 1) * p / 2
		k -= (x - 1) * p
		i += 1
	if i == n:
		print('YES')
	else:
		print('No')
	return
t = int(input())
for _ in range(t):
	solve()


def solve():
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	hp = sorted(zip(p, h))
	del h, p
	dmg = 0
	for (i, item) in enumerate(hp):
		if item[1] <= dmg:
			continue
		if i != 0:
			k -= item[0]
		if k > 0:
			dmg += k
			while item[1] > dmg:
				k -= item[0]
				if k < 0:
					break
				dmg += k
		if item[1] > dmg:
			print('NO')
			return
	print('YES')
for _ in range(int(input())):
	solve()


import sys

def main():
	for _ in range(int(input())):
		(n, m) = list(map(int, input().split()))
		a = list(map(int, input().split()))
		b = list(map(int, input().split()))
		v = [(b[i], a[i]) for i in range(n)]
		v.sort()
		sum = 0
		k = 0
		cnt = 0
		while cnt < n and m > 0:
			k += m
			p = v[cnt]
			while p[1] <= k and cnt < n:
				cnt += 1
				if cnt < n:
					p = v[cnt]
			m -= p[0]
		if cnt == n:
			print('YES')
		else:
			print('NO')
main()


import math

def func(n, k, h, p):
	z = list(zip(h, p))
	z.sort(key=lambda x: x[0])
	minr = [0 for i in range(n)]
	minr[-1] = z[-1][1]
	for i in range(n - 2, -1, -1):
		minr[i] = min(minr[i + 1], z[i][1])
	cv = 0
	cp = 0
	while k > 0:
		cv += k
		while cp < n and z[cp][0] <= cv:
			cp += 1
		if cp == n:
			return 'YES'
		k -= minr[cp]
	return 'NO'
q = int(input())
for i in range(q):
	(n, k) = list(map(int, input().split()))
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	print(func(n, k, h, p))


from heapq import heapify
import heapq
import math
import sys
input = sys.stdin.readline
inp = sys.stdin.readline

def input():
	return inp().strip()

def ii():
	return int(input())

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

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

def solve():
	(n, k) = mi()
	health = li()
	power = li()
	heap = []
	for (p, h) in zip(power, health):
		heapq.heappush(heap, (p, h))
	curr = k
	while k > 0 and heap:
		while heap and heap[0][1] <= curr:
			heapq.heappop(heap)
		if heap:
			k -= heap[0][0]
			curr += k
	if not heap:
		print('YES')
	else:
		print('NO')

def main():
	for _ in range(ii()):
		solve()
main()


import heapq
from collections import defaultdict, Counter
graph = defaultdict(set)

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

def solve(k, health, power):
	monsters = sorted(((p, h) for (p, h) in zip(power, health)))
	damage_done = 0
	i = 0
	while k > 0:
		damage_done += k
		while i < len(monsters) and monsters[i][1] <= damage_done:
			i += 1
		if i == len(monsters):
			return 'YES'
		k -= monsters[i][0]
	return 'NO'
for _ in range(int(input())):
	(n, k) = listinput()
	h = listinput()
	p = listinput()
	print(solve(k, h, p))


def solution():
	(n, k) = list(map(int, input().split()))
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	occurrences = {}
	p_unique = []
	for x in p:
		if x in occurrences:
			occurrences[x] += 1
		else:
			occurrences[x] = 1
			p_unique.append(x)
	p_unique.sort()
	tuples_sorted = sorted(zip(h, p))
	tuples_sorted = zip(*tuples_sorted)
	(h, p) = [list(tuple) for tuple in tuples_sorted]
	ptr = 0
	ptr_unique = 0
	total_k = k
	minimun_power = p_unique[ptr_unique]
	while ptr < n:
		if k <= 0:
			print('NO')
			return
		if h[ptr] > total_k:
			k -= minimun_power
			total_k += k
		else:
			occurrences[p[ptr]] -= 1
			while occurrences[p_unique[ptr_unique]] == 0:
				ptr_unique += 1
				if ptr_unique == len(p_unique):
					break
			if ptr_unique != len(p_unique):
				minimun_power = p_unique[ptr_unique]
			ptr += 1
	print('YES')
for _ in range(int(input())):
	solution()


for _ in range(int(input())):
	(monsters, att_dmg) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	h_p = sorted([[h[i], p[i]] for i in range(monsters)], key=lambda x: x[1], reverse=True)
	cur_dealt = 0
	while True:
		if att_dmg <= 0:
			print('NO')
			break
		cur_dealt += att_dmg
		while h_p:
			if h_p[-1][0] - cur_dealt > 0:
				att_dmg -= h_p[-1][1]
				break
			h_p.pop()
		else:
			print('YES')
			break


import sys, math, cmath, time
from bisect import bisect_left
from bisect import bisect_right
start_time = time.time()

def solve(t):
	(n, k) = map(int, inps())
	l = [int(p) for p in input().split()]
	d = {}
	for i in l:
		d[i] = 0
	l1 = [int(p) for p in input().split()]
	f = []
	for i in range(n):
		f.append([l[i], l1[i]])
	f = sorted(f, key=lambda x: (x[1], x[0]))
	i = 0
	tot = k
	while k > 0 and i < n:
		if tot < f[i][0]:
			k = k - f[i][1]
			tot = tot + k
		else:
			i = i + 1
	if i == n:
		print('YES')
	else:
		print('NO')

def main():
	testcases = 1
	testcases = inp()
	for t in range(1, testcases + 1):
		solve(t)

def inp():
	return int(input())

def inps():
	return input().split()
ONLINE_JUDGE = __debug__
if ONLINE_JUDGE:
	input = sys.stdin.readline
main()


for x in range(int(input())):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	zipped = zip(h, p)
	res = sorted(zipped, key=lambda sol: sol[1])
	dem = k
	index = 0
	while index < n and k > 0:
		if res[index][0] <= dem:
			index += 1
		else:
			dem += k - res[index][1]
			k -= res[index][1]
	if index == n:
		print('YES')
	else:
		print('NO')


import math
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	arr = [(p[i], -1 * h[i]) for i in range(n)]
	arr.sort()
	tot = 0
	possible = True
	t = False
	for (pi, hi) in arr:
		hi = -1 * hi
		if hi > tot:
			if t:
				k -= pi
			hi -= tot
			while hi > 0 and k > 0:
				hi -= k
				tot += k
				if hi > 0:
					k -= pi
				else:
					t = True
		else:
			hi = 0
		if k < 0 or (k == 0 and hi != 0):
			possible = False
			break
	if possible:
		print('YES')
	else:
		print('NO')


from dataclasses import dataclass

def dumb_kill(monster, atk, dmg):
	monster.hp -= dmg
	while True:
		atk -= monster.atk
		monster.hp -= atk
		dmg += atk
		if monster.hp <= 0:
			break
		if atk <= 0:
			break
	return (dmg, atk)

def kill(monster, atk, dmg):
	return dumb_kill(monster, atk, dmg)

@dataclass
class Monster:
	atk: int
	hp: int

def solve(a, H, P):
	atk = a
	dmg = 0
	monsters = [Monster(atk=p, hp=h) for (h, p) in zip(H, P)]
	monsters = sorted(monsters, key=lambda m: m.atk)
	atk += monsters[0].atk
	for monster in monsters:
		if dmg >= monster.hp:
			continue
		(dmg, atk) = kill(monster, atk, dmg)
		if atk <= 0:
			break
	if atk <= 0:
		return 'NO'
	else:
		return 'YES'

def run(i):
	(n, attack) = (int(x) for x in input().split())
	healths = [int(x) for x in input().split()]
	powers = [int(x) for x in input().split()]
	ans = solve(attack, healths, powers)
	print(ans)
for i in range(int(input())):
	run(i)


import heapq

def solve():
	(n, k) = list(map(int, input().split()))
	health = list(map(int, input().split()))
	atk = list(map(int, input().split()))
	q = []
	for (i, a) in enumerate(atk):
		heapq.heappush(q, (a, i))
	atkSoFar = 0
	while k > 0 and q:
		atkSoFar += k
		while q and health[q[0][1]] <= atkSoFar:
			heapq.heappop(q)
		if q:
			k -= q[0][0]
	if q:
		print('NO')
	else:
		print('YES')
T = int(input())
for _ in range(T):
	solve()


from itertools import accumulate, repeat
from operator import getitem
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	a = sorted(zip(h, p), key=lambda t: t[0])
	mins = list(accumulate(map(getitem, reversed(a), repeat(1)), min))
	mins.reverse()
	(i, acc) = (0, 0)
	while m > 0:
		acc += m
		while i < n and acc >= a[i][0]:
			i += 1
		if i == n:
			break
		m -= mins[i]
	print(('NO', 'YES')[i == n])


from collections import defaultdict
for _ in range(int(input())):
	(n, k) = list(map(int, input().split()))
	lh = list(map(int, input().split()))
	lp = list(map(int, input().split()))
	d = defaultdict(int)
	for x in range(n):
		d[lp[x]] = max(d[lp[x]], lh[x])
	lp.sort()
	crr = k
	x = 0
	f = 0
	while k > 0:
		while d[lp[x]] <= crr:
			x += 1
			if x == n:
				f = 1
				break
		if x == n:
			break
		k -= lp[x]
		crr += k
	if f:
		print('YES')
	else:
		print('NO')


def solve(n, k, h, p):
	monsters = sorted(((power, health) for (power, health) in zip(p, h)))
	damage_done = 0
	monster_index = 0
	while k > 0:
		damage_done += k
		while monster_index < len(monsters) and monsters[monster_index][1] <= damage_done:
			monster_index += 1
		if monster_index == len(monsters):
			return 'YES'
		k -= monsters[monster_index][0]
	return 'NO'
t = int(input())
for _ in range(t):
	(n, k) = [int(component) for component in input().split(' ')]
	h = [int(component) for component in input().split(' ')]
	p = [int(component) for component in input().split(' ')]
	print(solve(n, k, h, p))


import heapq
for _ in range(int(input())):
	(_, k) = map(int, input().split())
	h = tuple(map(int, input().split()))
	p = tuple(map(int, input().split()))
	a = list(zip(p, h))
	heapq.heapify(a)
	min_h = 0
	while True:
		min_h += k
		while a:
			(p, h) = a[0]
			if h <= min_h:
				heapq.heappop(a)
				continue
			k -= p
			break
		if not a:
			print('YES')
			break
		if k <= 0:
			print('NO')
			break


def solve():
	(_, atack) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	a = sorted((list(i) for i in zip(p, h)))
	cum_atack = 0
	pointer = 0
	while atack > 0:
		cum_atack += atack
		while pointer < len(a) and a[pointer][1] <= cum_atack:
			pointer += 1
		if pointer == len(a):
			break
		atack -= a[pointer][0]
	if pointer == len(a):
		print('YES')
	else:
		print('NO')
for _ in range(int(input())):
	solve()


for _ in range(int(input())):
	(n, k) = [int(x) for x in input().split(' ')]
	h = [int(x) for x in input().split(' ')]
	p = [int(x) for x in input().split(' ')]
	m = sorted(zip(p, h))
	attack_now = k
	pos = 0
	all_damage = 0
	while attack_now > 0:
		all_damage += attack_now
		while pos < n and all_damage >= m[pos][1]:
			pos += 1
		if pos < n:
			attack_now -= m[pos][0]
		if pos == n:
			break
	if pos == n:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	L = []
	for i in range(n):
		L.append((p[i], h[i]))
	L.sort()
	f = True
	a = k
	i = 0
	while i < n:
		(b, c) = L[i]
		if c > a:
			if k < b:
				f = False
				break
			else:
				k -= b
				a += k
		else:
			i += 1
	if f:
		print('YES')
	else:
		print('NO')


import heapq

def incerenate(k, hstr, pstr):
	monsterh = hstr.split()
	monsterp = pstr.split()
	intmon = []
	i = 0
	while i < len(monsterh):
		intmon.append((int(monsterp[i]), int(monsterh[i])))
		i = i + 1
	totalpower = 0
	heapq.heapify(intmon)
	while True:
		totalpower = totalpower + k
		while intmon[0][1] - totalpower <= 0:
			heapq.heappop(intmon)
			if len(intmon) == 0:
				return True
		k = k - intmon[0][0]
		if k <= 0:
			if len(intmon) == 0:
				return True
			else:
				return False
		if len(intmon) == 0:
			return True
for j in range(int(input())):
	ing = input()
	k = int(ing.split()[1])
	if incerenate(k, input(), input()):
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, r) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	z = list(sorted(zip(p, h)))
	k = r
	i = 0
	while i < n and r != 0:
		if z[i][1] <= k:
			i += 1
		else:
			r = max(0, r - z[i][0])
			k += r
	if k < max(h):
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	nums = [[a, b] for (a, b) in zip(h, p)]
	nums.sort()
	for i in range(n - 2, -1, -1):
		nums[i][1] = min(nums[i][1], nums[i + 1][1])
	lei = k
	for (i, (x, y)) in enumerate(nums):
		while lei < x:
			k -= y
			lei += k
			if k < 0:
				break
	if lei >= nums[-1][0]:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	h = [int(x) for x in input().split()]
	p = [int(x) for x in input().split()]
	d = []
	for i in range(n):
		t = (h[i], p[i])
		d.append(t)
	d = sorted(d, key=lambda x: x[1])
	i = 0
	m = d[0][1]
	hi = k
	while i < n:
		if hi < d[i][0]:
			m = d[i][1]
			k -= m
			hi += k
		else:
			i += 1
		if k < 0:
			break
	if max(h) > hi:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	z = list(zip(p, h))
	z.sort()
	tongst = k
	M = max(h)
	i = 0
	x = len(z)
	while i < x and k != 0:
		if z[i][1] > tongst:
			k = max(0, k - z[i][0])
			tongst = tongst + k
		else:
			i = i + 1
	if tongst < M:
		print('NO')
	else:
		print('YES')


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	mx = max(h)
	p = list(map(int, input().split()))
	c = list(sorted(zip(p, h)))
	sum = k
	i = 0
	while i < len(c) and k != 0:
		if sum < c[i][1]:
			k = k - c[i][0]
			if k < 0:
				k = 0
			sum = sum + k
		else:
			i = i + 1
	if sum >= mx:
		print('YES')
	else:
		print('NO')


from heapq import heapify, heappop, heappush
for tcase in range(int(input())):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	monsters = sorted(zip(p, h))
	damage = 0
	i = 0
	while i < n and k > 0:
		damage += k
		while i < n and monsters[i][1] <= damage:
			i += 1
		if i < n:
			k -= monsters[i][0]
	print('YES' if i == n else 'NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	d = {}
	for i in range(n):
		if p[i] not in d:
			d[p[i]] = h[i]
		elif h[i] > d[p[i]]:
			d[p[i]] = h[i]
	arr = sorted(list(d.keys()))
	dmg = 0
	for x in arr:
		d[x] -= dmg
		while d[x] - k > 0:
			d[x] -= k
			dmg += k
			k -= x
			if k <= 0:
				break
	print('YES' if k > 0 else 'NO')


import sys, os
if os.getlogin() == 'arun':
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
from collections import defaultdict
import math
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	hp = list(map(int, input().split()))
	po = list(map(int, input().split()))
	minval = 2 ** 40
	fin = [[hp[i], po[i]] for i in range(n)]
	fin = sorted(fin, key=lambda x: x[0])
	mn = [0 for x in range(n)]
	mn[-1] = fin[-1][1]
	for i in range(-1, -n - 1, -1):
		if fin[i][1] < minval:
			minval = fin[i][1]
		fin[i][1] = minval
	sm = 0
	i = 0
	while i < n and k > 0:
		sm += k
		while i < n and fin[i][0] <= sm:
			i += 1
		if i < n:
			k -= fin[i][1]
	print('YES' if i == n else 'NO')


import math
t = int(input())
for _ in range(0, t):
	inputs = [int(num) for num in input().split()]
	n = inputs[0]
	k = inputs[1]
	list2 = [int(num) for num in input().split()]
	list1 = [int(num) for num in input().split()]
	zipped_lists = zip(list1, list2)
	sorted_pairs = sorted(zipped_lists)
	tuples = zip(*sorted_pairs)
	(list1, list2) = [list(tuple) for tuple in tuples]
	dam = 0
	c = 0
	for i in range(0, len(list1)):
		if list2[i] > dam:
			list2[i] = list2[i] - dam
			if i != 0:
				k = k - list1[i]
			while list2[i] > 0:
				list2[i] = list2[i] - k
				dam += k
				if list2[i] > 0:
					k = k - list1[i]
				if k <= 0:
					break
			if list2[i] <= 0:
				c += 1
			if k <= 0:
				break
		else:
			c += 1
	if c == n:
		print('YES')
	else:
		print('NO')


for a in range(0, int(input())):
	(n, k) = map(int, input().split())
	h = [int(x) for x in input().split()]
	p = [int(x) for x in input().split()]
	hp = sorted(zip(p, h))
	current_dmg = k
	pos = 0
	total_dmg = 0
	while current_dmg > 0:
		total_dmg += current_dmg
		while pos < n and total_dmg >= hp[pos][1]:
			pos += 1
		if pos < n:
			current_dmg -= hp[pos][0]
		if pos == n:
			break
	if pos == n:
		print('YES')
	else:
		print('NO')


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	l = []
	f = 0
	for i in range(n):
		l.append((p[i], h[i]))
	l = sorted(l)
	cur = 0
	for i in range(n):
		while l[i][1] - cur > k:
			cur += k
			k = k - l[i][0]
			if k <= 0:
				f = 1
				break
			continue
		i += 1
	if f == 0:
		print('YES')
	else:
		print('NO')
	t = t - 1


cases = int(input())
for i in range(cases):
	(n, k) = [int(i) for i in input().split()]
	h = [int(i) for i in input().split()]
	p = [int(i) for i in input().split()]
	c = []
	for i in range(len(h)):
		c.append((p[i], h[i]))
	c.sort(key=lambda x: x[0])
	j = 0
	sum1 = k
	while j < len(h) and k != 0:
		if sum1 < c[j][1]:
			k = k - c[j][0]
			if k < 0:
				k = 0
			sum1 = sum1 + k
		else:
			j = j + 1
	if sum1 >= max(h):
		print('YES')
	else:
		print('NO')


t = int(input())
result = []
for i in range(t):
	(n, k) = list(map(int, input().split(' ')))
	hi = list(map(int, input().split(' ')))
	pi = list(map(int, input().split(' ')))
	d = {}
	for j in range(n):
		if pi[j] not in d:
			d[pi[j]] = hi[j]
		elif hi[j] > d[pi[j]]:
			d[pi[j]] = hi[j]
	l = list(d.keys())
	l.sort()
	totalDamage = 0
	for j in l:
		d[j] -= totalDamage
		while d[j] - k > 0:
			d[j] -= k
			totalDamage += k
			k -= j
			if k <= 0:
				break
	if k > 0:
		result.append('YES')
	else:
		result.append('NO')
for i in result:
	print(i)


t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().split()]
	h = [int(i) for i in input().split()]
	p = [int(i) for i in input().split()]
	m = sorted(zip(h, p), key=lambda i: i[1])
	i = 0
	d = 0
	dam = False
	while i < len(m):
		if d >= m[i][0]:
			i += 1
		elif k <= 0:
			break
		else:
			if dam:
				k -= m[i][1]
				dam = False
			d += k
			if k > d:
				k -= m[i][1]
			else:
				dam = True
	if i == len(m):
		print('YES')
	else:
		print('NO')


t = int(input())
for i in range(t):
	(x, y) = map(int, input().split(' '))
	hrr = list(map(int, input().split(' ')))
	prr = list(map(int, input().split(' ')))
	arr = []
	for j in range(x):
		arr.append([prr[j], j])
	arr.sort()
	temp = y
	k = 0
	while k < x and y > 0:
		if hrr[arr[k][1]] - temp > 0:
			y -= arr[k][0]
			temp += y
		else:
			k += 1
	if y <= 0:
		print('NO')
	else:
		print('YES')


import heapq
iter = int(input())
for _ in range(iter):
	(n, k) = list(map(int, input().split(' ')))
	h = list(map(int, input().split(' ')))
	p = list(map(int, input().split(' ')))
	total_damage = 0
	a = list(zip(p, h))
	heapq.heapify(a)
	while len(a):
		total_damage += k
		while a[0][1] <= total_damage:
			heapq.heappop(a)
			if len(a) == 0:
				break
		if len(a) == 0:
			break
		d = a[0][0]
		k -= d
		if k <= 0:
			break
	if k > 0:
		print('YES')
	else:
		print('NO')


import math
from collections import Counter, deque
from heapq import heapify, heappop, heappush
for i in range(int(input())):
	(n, k) = map(int, input().split())
	arr1 = [int(x) for x in input().split()]
	arr2 = [int(x) for x in input().split()]
	arr = [[arr2[i], arr1[i]] for i in range(n)]
	p = []
	count = 0
	for j in arr:
		if j[1] > k:
			p.append(j)
			count += 1
	if count == 0:
		print('YES')
		continue
	res = 0
	flag = 0
	heapify(p)
	while len(p) != 0:
		x = heappop(p)
		x[1] -= res
		while x[1] > 0:
			if k <= 0:
				flag = 1
				break
			if x[1] <= 0:
				break
			res += k
			x[1] -= k
			k -= x[0]
		if flag == 1:
			break
	if flag == 1:
		print('NO')
	else:
		print('YES')


import heapq as hp
cases = int(input())
inp = []
for _ in range(cases):
	inp.append([])
	for x in range(3):
		inp[-1].append([int(y) for y in input().split(' ')])
for inpt in inp:
	hpp = []
	hp.heapify(hpp)
	for (h, p) in zip(inpt[1], inpt[2]):
		hp.heappush(hpp, (p, h))
	(k, dm) = (inpt[0][1], 0)
	while k != 0 and hpp:
		dm += k
		while hpp and hpp[0][1] <= dm:
			hp.heappop(hpp)
		if hpp:
			k = max(0, k - hpp[0][0])
	print('YES') if k != 0 else print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	m = max(h)
	arr = [[h[i], p[i]] for i in range(n)]
	arr = sorted(arr, key=lambda x: x[0])
	arr = sorted(arr, key=lambda x: x[1])
	curr = 0
	m -= k
	i = 0
	curr += k
	while i < n and m > 0 and (k > 0):
		if curr >= arr[i][0]:
			i += 1
			continue
		k -= arr[i][1]
		m -= k
		curr += k
	if m > 0:
		print('NO')
	else:
		print('YES')


t = int(input())
for _ in range(t):
	(n, k) = list(map(int, input().split()))
	health = list(map(int, input().split()))
	power = list(map(int, input().split()))
	alive = list(range(n))
	order = []
	for i in range(n):
		order.append([power[i], health[i]])
	order.sort(key=lambda x: (x[0], x[1]))
	maxhealth = max(health)
	damage = 0
	i = 0
	while k > 0 and i < n and (damage < maxhealth):
		damage += k
		while order[i][1] <= damage and i < n - 1:
			i += 1
		if i < n:
			k -= order[i][0]
		else:
			break
	if damage >= maxhealth:
		print('YES')
	else:
		print('NO')


import sys
t = int(sys.stdin.readline())
for i in range(t):
	(n, k) = map(int, sys.stdin.readline().split())
	lsth = list(map(int, sys.stdin.readline().split()))
	lstp = list(map(int, sys.stdin.readline().split()))
	vec = []
	for j in range(n):
		vec.append([lstp[j], lsth[j]])
	vec.sort(key=lambda x: x[0])
	er = 0
	ele = 0
	ind = 0
	while True:
		if k <= 0:
			er += 1
			break
		ele += k
		e = 0
		while True:
			if ind > n - 1:
				e += 1
				break
			p = vec[ind][0]
			h = vec[ind][1] - ele
			if h > 0:
				break
			ind += 1
		if ind > n - 1:
			break
		k -= vec[ind][0]
	if er > 0:
		print('NO')
	else:
		print('YES')


import sys, collections
input = sys.stdin.readline
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	a = list(map(int, input().split()))
	b = list(map(int, input().split()))
	l = []
	for i in range(n):
		l.append([a[i], b[i]])
	l.sort(key=lambda x: x[1], reverse=True)
	s = collections.deque()
	s.append(l[0])
	for i in range(1, n):
		if s[-1][1] == l[i][1]:
			s[-1][0] = max(s[-1][0], l[i][0])
		else:
			s.append(l[i])
	r = 0
	while s:
		if s[-1][0] - r > 0:
			if k <= 0:
				print('NO')
				break
			elif k >= s[-1][0] - r:
				s.pop()
				r += k
				while len(s) > 0:
					if s[-1][0] - r > 0:
						k = k - s[-1][1]
						break
					else:
						s.pop()
				else:
					print('YES')
					break
			else:
				r += k
				k = k - s[-1][1]
		else:
			s.pop()
	else:
		print('YES')


def ii(num=False):
	i = input().split()
	if num:
		return int(i[0])
	try:
		return list(map(int, i))
	except Exception:
		return i

def gcd(a, b):
	if a == 0:
		return b
	return gcd(b % a, a)
for _ in range(ii(1)):
	(n, k) = ii()
	h = ii()
	p = ii()
	a = sorted(list(zip(p, h)))
	accDamage = 0
	i = 0
	while i < n:
		(cp, ch) = a[i]
		if accDamage >= ch:
			i += 1
		else:
			accDamage += k
			while i < n and a[i][1] <= accDamage:
				i += 1
			if i == n:
				break
			k -= a[i][0]
			if k <= 0 and (not all([accDamage >= hh for (pp, hh) in a])):
				break
	print('YES' if i == n else 'NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	d = 0
	monsters = sorted(zip(h, p), key=lambda x: x[1])
	while k > 0:
		d += k
		for (hp, power) in monsters:
			if hp > d:
				k -= power
				break
		else:
			break
	else:
		print('NO')
		continue
	print('YES')


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	l1 = list(map(int, input().split()))
	l2 = list(map(int, input().split()))
	l3 = []
	for i in range(n):
		l3.append([l1[i], l2[i]])
	l3.sort()
	min = l3[n - 1][1]
	for i in range(n - 2, -1, -1):
		if min > l3[i][1]:
			min = l3[i][1]
		else:
			l3[i][1] = min
	j = k
	index = 0
	found = False
	while k > 0 and index < n:
		while index < n and l3[index][0] <= j:
			index += 1
		if index == n:
			found = True
			break
		k -= l3[index][1]
		j += k
	if index < n:
		print('NO')
	if found:
		print('YES')


import operator
import itertools as it
import functools as ft
for _ in range(int(input())):
	(n, k) = map(int, input().split())
	m = list(zip(map(int, input().split()), map(int, input().split())))
	m.sort(key=lambda monster: monster[1])
	dmg = k
	i = 0
	while i < len(m):
		if m[i][0] <= dmg:
			i += 1
		elif m[i][1] >= k:
			print('NO')
			break
		else:
			k = max(0, k - m[i][1])
			dmg += k
	if i == len(m):
		print('YES')


for _ in range(int(input())):
	(n, k) = tuple(map(int, input().split()))
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	ph = {}
	for i in range(n):
		ph[p[i]] = max(ph.get(p[i], 0), h[i])
	(pu, hu) = ([], [])
	for pi in sorted(ph.keys(), reverse=True):
		pu.append(pi)
		hu.append(ph[pi])
	a = 1
	total_damage = 0
	while k > 0 and len(pu) != 0:
		(x, y) = (pu[-1], hu[-1])
		total_damage += k
		if total_damage >= y:
			while len(hu) > 0 and hu[-1] - total_damage <= 0:
				pu.pop()
				hu.pop()
			a = 1
		else:
			a += 1
		k -= pu[-1] if len(pu) > 0 else 0
	print('YES' if len(pu) == 0 else 'NO')


from bisect import bisect_right
t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().strip().split()]
	h = [int(i) for i in input().strip().split()]
	p = [int(i) for i in input().strip().split()]
	(h, p) = zip(*sorted(zip(h, p)))
	min_p = [None for i in range(n)]
	curr_min = float('inf')
	for i in range(n - 1, -1, -1):
		curr_min = min(curr_min, p[i])
		min_p[i] = curr_min
	curr_damage = k
	check = False
	while True:
		i = bisect_right(h, curr_damage)
		if i >= n:
			check = True
			break
		k -= min_p[i]
		if k <= 0:
			break
		curr_damage += k
	if check:
		print('YES')
	else:
		print('NO')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	health = list(map(int, input().split()))
	power = list(map(int, input().split()))
	main = []
	for i in range(n):
		main.append([power[i], health[i]])
	main.sort()
	k1 = k
	s = 0
	for j in range(n):
		sta = 0
		while main[j][1] > 0:
			if k < 0:
				break
			if sta == 0:
				main[j][1] -= k1
			else:
				main[j][1] -= k
			if main[j][1] <= 0:
				break
			else:
				k -= main[j][0]
			if k < 0:
				break
			k1 += k
			sta = 1
		if k <= 0:
			if main[-1][1] > 0:
				s = 1
				print('NO')
				break
				s = 1
	if s != 1:
		print('YES')


for _ in range(int(input())):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	for i in range(n):
		h[i] = (i, h[i])
		p[i] = (i, p[i])
	h.sort(key=lambda x: x[1])
	p.sort(key=lambda x: x[1])
	dead = set()
	(i, j) = (0, 0)
	damage = 0
	while i < n and j < n and (k > 0):
		damage += k
		while i < n:
			if h[i][1] <= damage:
				dead.add(h[i][0])
			else:
				break
			i += 1
		while j < n:
			if p[j][0] not in dead:
				k -= p[j][1]
				break
			j += 1
	if len(dead) == n:
		print('YES')
	else:
		print('NO')


t = int(input())
for _ in range(t):
	(n, k) = [int(_) for _ in input().split()]
	hp = [int(_) for _ in input().split()]
	d = [int(_) for _ in input().split()]
	h = []
	dc = {}
	for i in range(len(hp)):
		h.append((hp[i], d[i]))
		dc[d[i]] = dc.get(d[i], 0) + 1
	h.sort(reverse=True)
	d.sort(reverse=True)
	limit = 0
	while True:
		limit += k
		while len(h) > 0 and h[-1][0] <= limit:
			dc[h[-1][1]] -= 1
			h.pop()
		if len(h) == 0:
			print('YES')
			break
		while dc[d[-1]] == 0:
			d.pop()
		k -= d[-1]
		if k <= 0:
			print('NO')
			break


from collections import deque
from heapq import *
t = int(input())
for _ in range(t):
	(n, k) = [int(i) for i in input().split()]
	h = [int(i) for i in input().split()]
	p = [int(i) for i in input().split()]
	p_heap = []
	h_heap = []
	killed = set()
	for i in range(n):
		p_heap.append((p[i], i))
		h_heap.append((h[i], i))
	h_heap.sort()
	p_heap.sort()
	cur = 0
	removed = set()
	ptr = 0
	ptr2 = 0
	while k > 0 and ptr < n:
		cur += k
		while ptr < n and cur >= h_heap[ptr][0]:
			removed.add(h_heap[ptr][1])
			ptr += 1
		while ptr2 < n and p_heap[ptr2][1] in removed:
			ptr2 += 1
		if ptr2 < n:
			k -= p_heap[ptr2][0]
	if ptr == n:
		print('YES')
	else:
		print('NO')


import os
import math
import collections
import bisect
import functools
import itertools
import heapq

def solve(h, p, n, k):
	q = [[p[i], i] for i in range(n)]
	r = [0] * n
	heapq.heapify(q)
	x = k
	while k > 0:
		while q and h[q[0][1]] - (x - r[q[0][1]]) <= 0:
			heapq.heappop(q)
		if not q:
			return 'YES'
		h[q[0][1]] -= x - r[q[0][1]]
		r[q[0][1]] = x
		k -= q[0][0]
		x += k
	return 'NO'
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	print(solve(h, p, n, k))


t = int(input())
while t:
	t -= 1
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	p_heap = []
	for i in range(n):
		p_heap.append((p[i], h[i]))
	p_heap = sorted(p_heap, key=lambda x: x[0])
	dec_pow = k
	while k > 0 and p_heap:
		while p_heap and p_heap[0][1] <= dec_pow:
			p_heap.pop(0)
		if not p_heap:
			break
		k -= p_heap[0][0]
		dec_pow += k
	print('YES' if not p_heap else 'NO')


t = int(input())
while t > 0:
	(n, k) = map(int, input().split())
	H = list(map(int, input().split()))
	P = list(map(int, input().split()))
	h = []
	p = []
	for i in range(n):
		h.append((i, H[i]))
		p.append((H[i], P[i]))
	count = k
	left = 0
	right = 0
	h.sort(key=lambda x: x[1])
	p.sort(key=lambda x: x[1])
	ss = 0
	DEL = p[0][1]
	while count > 0:
		while left < n and k >= h[left][1]:
			left += 1
		if left == n:
			ss = 1
			break
		while right < n and k >= p[right][0]:
			right += 1
		DEL = p[right][1]
		count -= DEL
		k += count
	if ss:
		print('YES')
	else:
		print('NO')
	t -= 1


def fun(lp, lh, n, k):
	l = []
	for i in range(n):
		l.append((lp[i], lh[i]))
	l.sort(key=lambda x: x[0])
	cnt = k
	while len(l) != 0:
		if k <= 0:
			print('NO')
			return
		elif l[0][1] - cnt > 0:
			k = k - l[0][0]
			cnt = cnt + k
		elif l[0][1] - cnt <= 0:
			l.remove(l[0])
	print('YES')
t = int(input())
for j in range(t):
	(n, k) = map(int, input().split())
	lh = list(map(int, input().split()))
	lp = list(map(int, input().split()))
	fun(lp, lh, n, k)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	h = list(map(int, input().split()))
	p = list(map(int, input().split()))
	a = []
	mx = max(h)
	for i in range(n):
		a.append((h[i], p[i]))
	a.sort()
	z = k
	cnt = 0
	pm = [0] * n
	pm[n - 1] = a[n - 1][1]
	for j in range(n - 2, -1, -1):
		pm[j] = min(pm[j + 1], a[j][1])
	while k > 0 and mx > 0 and (cnt < n):
		while cnt < n and z >= a[cnt][0]:
			cnt += 1
		mx -= k
		if cnt < n:
			k -= pm[cnt]
			if k > 0:
				z += k
	if mx <= 0:
		print('YES')
	else:
		print('NO')


import heapq
t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	hh = list(map(int, input().split()))
	pp = list(map(int, input().split()))
	hh = [[x, i] for (i, x) in enumerate(hh)]
	pp = [[x, i] for (i, x) in enumerate(pp)]
	heapq.heapify(hh)
	heapq.heapify(pp)
	rep = set()
	lei = 0
	while k > 0 and hh and pp:
		lei += k
		while hh and hh[0][0] <= lei:
			(a, b) = heapq.heappop(hh)
			rep.add(b)
		while pp and pp[0][1] in rep:
			heapq.heappop(pp)
		if pp:
			k -= pp[0][0]
	if n == len(rep):
		print('YES')
	else:
		print('NO')


from heapq import heapify
import heapq
import sys
input = sys.stdin.readline
inp = sys.stdin.readline

def input():
	return inp().strip()

def ii():
	return int(input())

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

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

def solve():
	(n, k) = mi()
	health = li()
	x = li()
	power = []
	for (tk, v) in enumerate(x):
		heapq.heappush(power, (v, tk))
	curr = k
	maxH = max(health)
	while k > 0 and maxH > 0 and power:
		(currV, currK) = heapq.heappop(power)
		if health[currK] <= curr:
			continue
		k -= currV
		curr += k
		heapq.heappush(power, (currV, currK))
	if maxH - curr <= 0:
		print('YES')
		return
	else:
		print('NO')

def main():
	for _ in range(ii()):
		solve()
main()