Read problem statements in [Russian]

Chef has been searching for a good motivational movie that he can watch during his exam time. His hard disk has $X$ GB of space remaining. His friend has $N$ movies represented with $(S_{i}, R_{i})$  representing (space required, IMDB rating). Help Chef choose the single best movie (highest IMDB rating) that can fit in his hard disk.

------  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 $X$.
$N$ lines follow. For each valid $i$, the $i$-th of these lines contains two space-separated integers $S_{i}$ and $R_{i}$.

------  Output ------
For each test case, print a single line containing one integer - the highest rating of an IMDB movie which Chef can store in his hard disk.

------  Constraints ------
$1 ≤ T ≤ 10$
$1 ≤ N ≤ 5 \cdot 10^{4}$
$1 ≤ X ≤ 10^{9}$
$1 ≤ S_{i}, R_{i} ≤ 10^{9}$ for each valid $i$
$X ≥ S_{i}$ for atleast one valid $i$

------  Subtasks ------
Subtask #1 (100 points): original constraints

----- Sample Input 1 ------ 
3

1 1

1 1

2 2

1 50

2 100

3 2

1 51

3 100

2 50
----- Sample Output 1 ------ 
1

100 

51
----- explanation 1 ------ 
Example case 1: Since there is only $1$ movie available and requires space equivalent to the empty space in the hard disk, Chef can only obtain maximum IMDB rating of $1$.

Example case 2: Since out of the $2$ available movies, both can fit in the free memory, we only care to take the one with higher rating, i.e, rating of $max(50, 100) = 100$.

Example case 3: Since out of the $3$ available movies, only the first and the last movies fit in the free memory, we only care to take the one with higher rating amongst these $2$, i.e, rating of $\max(51, 50) = 51$.

Source: codechef | Difficulty: EASY
Tags: Implementation


Solutions:
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	d = {}
	imdb = []
	for i in range(n):
		(a, b) = map(int, input().split())
		d[b] = a
		imdb.append(b)
	imdb.sort(reverse=True)
	for i in imdb:
		if d[i] <= x:
			print(i)
			break


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = []
	for i in range(n):
		j = list(map(int, input().split()))
		a.append(j)
	m = 0
	for i in a:
		if i[0] <= x:
			m = max(m, i[1])
	print(m)


T = int(input())
for i in range(T):
	(N, X) = map(int, input().split(' '))
	s1 = []
	r1 = []
	for i in range(N):
		(s, r) = map(int, input().split(' '))
		if s <= X:
			s1.append(s)
			r1.append(r)
	print(max(r1))


t = int(input())
for tc in range(t):
	(n, x) = map(int, input().split())
	d = []
	for j in range(n):
		(s, r) = map(int, input().split())
		c = 0
		if s <= x:
			d.append(r)
	print(max(d))


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	l = []
	for i in range(n):
		(s, r) = map(int, input().split())
		if s <= x:
			l.append(r)
	print(max(l))


for i in range(int(input())):
	(mo, s) = map(int, input().split())
	m = 0
	for i in range(mo):
		(l, k) = map(int, input().split())
		if l <= s:
			if k > m:
				m = k
	print(m)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	d = []
	for i in range(n):
		l = list(map(int, input().split()))
		d.append(l)
	m = 0
	for i in d:
		if i[0] <= x:
			m = max(m, i[1])
	print(m)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	a = []
	for _ in range(n):
		(s, r) = map(int, input().split())
		if s <= x:
			a.append(r)
	print(max(a))


for i in range(int(input())):
	(N, X) = map(int, input().split())
	D = []
	for i in range(N):
		L = list(map(int, input().split()))
		D.append(L)
	m = 0
	for i in D:
		if i[0] <= X:
			m = max(m, i[1])
	print(m)


for i in range(int(input())):
	(q, w) = map(int, input().split())
	maxk = 0
	for i in range(q):
		(l, k) = map(int, input().split())
		if l <= w:
			if k > maxk:
				maxk = k
	print(maxk)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	maxx = 0
	for j in range(n):
		(s, r) = map(int, input().split())
		if s <= x:
			if r > maxx:
				maxx = r
	print(maxx)


for T in range(int(input())):
	(n, x) = map(int, input().split())
	maxRat = 0
	for i in range(n):
		(s, r) = map(int, input().split())
		if s <= x and r > maxRat:
			maxRat = r
	print(maxRat)


t = int(input())
for i in range(t):
	(n, x) = list(map(int, input().split()))
	m = -1
	for j in range(n):
		(size, rat) = list(map(int, input().split()))
		if size <= x:
			m = max(m, rat)
	print(m)


for i in range(int(input())):
	(N, X) = map(int, input().split())
	c = 0
	for j in range(N):
		(s, r) = map(int, input().split())
		if s <= X and r > c:
			c = r
	print(c)


def solve():
	(n, x) = map(int, input().split())
	max_rating = 0
	for i in range(n):
		(s, r) = map(int, input().split())
		if s <= x:
			max_rating = max(max_rating, r)
	print(max_rating)
t = int(input())
for i in range(t):
	solve()


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	l = []
	for j in range(n):
		s = list(map(int, input().split()))
		l.append(s)
	m = 0
	for i in l:
		if i[0] <= x:
			m = max(m, i[1])
	print(m)


for i in range(int(input())):
	(n, x) = [int(i) for i in input().split()]
	rat = -1
	while n:
		(a, b) = [int(i) for i in input().split()]
		if a <= x and rat < b:
			rat = b
		n = n - 1
	print(rat)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	imdb_highest = 0
	for _ in range(n):
		(s, r) = map(int, input().split())
		if s <= x:
			imdb_highest = max(imdb_highest, r)
	print(imdb_highest)


for i in range(int(input())):
	l = 0
	(a, b) = map(int, input().split())
	for i in range(a):
		(s, d) = map(int, input().split())
		if s <= b:
			if l < d:
				l = d
	print(l)


t = int(input())
while t > 0:
	(n, x) = map(int, input().split())
	l = []
	for i in range(n):
		(p, q) = map(int, input().split())
		l.append(p)
		l.append(q)
	a = 0
	for i in range(0, len(l), 2):
		if l[i] <= x:
			if l[i + 1] > a:
				a = l[i + 1]
	print(a)
	t = t - 1


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	l = []
	for i in range(n):
		(a, b) = map(int, input().split())
		l.append([a, b])
	l.sort(key=lambda x: x[1], reverse=True)
	for i in range(len(l)):
		if l[i][0] <= x:
			print(l[i][1])
			break


t = int(input())
for _ in range(t):
	(n, k) = map(int, input().split())
	cout = []
	for i in range(n):
		(s, r) = map(int, input().split())
		if s <= k:
			cout.append(r)
	print(max(cout))


for i in range(int(input())):
	(a, b) = map(int, input().split())
	l = []
	for i in range(a):
		(x, y) = map(int, input().split())
		if x <= b:
			l.append((x, y))
	l.sort(key=lambda x: x[1], reverse=True)
	print(l[0][1])


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	m = 0
	for i in range(n):
		(s, r) = map(int, input().split())
		if s <= x:
			m = max(m, r)
	print(m)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	r = 0
	for i in range(n):
		(a, b) = map(int, input().split())
		if a <= x and b > r:
			r = b
	print(r)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	ls = []
	for _ in range(n):
		ls.append(list(map(int, input().split())))
	ls.sort(key=lambda x: [-x[1], x[0]])
	for (s, r) in ls:
		if s <= x:
			print(r)
			break


t = int(input())
for _ in range(t):
	[n, x] = list(map(int, input().split()))
	l = []
	for i in range(n):
		a = list(map(int, input().split()))
		if a[0] <= x:
			l.append(a[1])
	print(max(l))


for i in range(int(input())):
	(n, x) = map(int, input().split())
	max1 = 0
	for i in range(n):
		(a, b) = map(int, input().split())
		if a <= x:
			if b > max1:
				max1 = b
	print(max1)


for i in range(int(input())):
	(N, X) = map(int, input().split())
	best = 0
	for i in range(N):
		(s, imdb) = map(int, input().split())
		if s <= X and imdb > best:
			best = imdb
	print(best)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	l = []
	for k in range(n):
		arr = list(map(int, input().split()))
		if arr[0] <= x:
			l.append(arr[-1])
	print(max(l))


for i in range(int(input())):
	l = []
	c = 0
	(n, k) = map(int, input().split())
	for i in range(n):
		(a, b) = map(int, input().split())
		if a <= k:
			c = max(c, b)
	print(c)


t = int(input())
for i in range(t):
	(N, X) = map(int, input().split())
	max = 0
	for j in range(N):
		(S, R) = map(int, input().split())
		if S <= X:
			if max < R:
				max = R
	print(max)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	max_rating = -1
	for i in range(n):
		(s, r) = map(int, input().split())
		if s <= x and max_rating < r:
			max_rating = r
	print(max_rating)


for i in range(int(input())):
	(N, X) = map(int, input().split())
	C = [list(map(int, f.split())) for f in [input() for x in range(N)]]
	C.sort(key=lambda x: x[1], reverse=True)
	for y in C:
		if y[0] <= X:
			print(y[1])
			break


for i in range(int(input())):
	(n, x) = map(int, input().split())
	max_r = 0
	for _ in range(n):
		(s, r) = map(int, input().split())
		if s <= x:
			if r > max_r:
				max_r = r
	print(max_r)


q = int(input())
for i in range(q):
	(n, x) = map(int, input().split())
	l = []
	l1 = []
	for j in range(n):
		(s, r) = map(int, input().split())
		if s <= x:
			l1.append(r)
	print(max(l1))


for t in range(int(input())):
	(n, x) = map(int, input().split())
	a = 0
	for i in range(n):
		(s, r) = map(int, input().split())
		if s <= x:
			if r > a:
				a = r
	print(a)


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	l = []
	for i in range(n):
		(si, ri) = map(int, input().split())
		if si <= x:
			l.append(ri)
	print(max(l))


from sys import stdin, stdout
input = stdin.readline
r_int = lambda : int(input())
m_int = lambda : map(int, input().split())
l_int = lambda : list(map(int, input()).split())

def solve():
	(n, x) = m_int()
	h = -1
	for _ in range(n):
		(s, r) = m_int()
		if s <= x:
			h = max(h, r)
	print(h)

def main():
	n_cases = r_int()
	for _ in range(n_cases):
		solve()
main()


def best_movie(n, x, movies):
	max_rating = 0
	for i in range(n):
		if movies[i][0] <= x and movies[i][1] > max_rating:
			max_rating = movies[i][1]
	return max_rating
t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	movies = [tuple(map(int, input().split())) for _ in range(n)]
	print(best_movie(n, x, movies))


for _ in range(int(input())):
	(movies, space_rem) = map(int, input().split())
	max_imdb = 0
	for i in range(movies):
		(space, imdb) = map(int, input().split())
		if space <= space_rem:
			if imdb > max_imdb:
				max_imdb = imdb
	print(max_imdb)


t = int(input())
for i in range(t):
	space_condition = input().split(' ')
	l_movie = []
	for j in range(int(space_condition[0])):
		movie = input().split(' ')
		if int(movie[0]) <= int(space_condition[1]):
			l_movie.append(int(movie[1]))
	l_movie.sort()
	print(l_movie[-1])


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	count = 0
	for j in range(a):
		(c, d) = map(int, input().split())
		if b >= c:
			if d > count:
				count = d
	print(count)


for i in range(int(input())):
	(N, X) = map(int, input().split())
	mx = 0
	for i in range(N):
		(A, B) = map(int, input().split())
		if A <= X:
			if B > mx:
				mx = B
	print(mx)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	s = []
	r = []
	for _ in range(n):
		(si, ri) = map(int, input().split())
		if si > x:
			pass
		else:
			s.append(si)
			r.append(ri)
	print(max(r))


for t in range(int(input())):
	(n, x) = map(int, input().split())
	hst = 0
	for j in range(n):
		(s, r) = map(int, input().split())
		if r > hst and s <= x:
			hst = r
	print(hst)


t = int(input())
for i in range(t):
	(n, x) = map(int, input().split())
	maxk = 0
	for i in range(n):
		(s, k) = map(int, input().split())
		if s <= x:
			if k > maxk:
				maxk = k
	print(maxk)


for i in range(int(input())):
	(x, y) = map(int, input().split())
	maxk = 0
	for i in range(x):
		(m, n) = map(int, input().split())
		if m <= y:
			if n > maxk:
				maxk = n
	print(maxk)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	li = []
	for i in range(n):
		(s, r) = map(int, input().split())
		if s <= x:
			li.append(r)
	print(max(li))


for i in range(int(input())):
	(n, x) = map(int, input().split())
	z = 0
	for j in range(n):
		(s, r) = map(int, input().split())
		if s > x:
			pass
		elif r > z:
			z = r
	print(z)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	res = 0
	for _ in range(n):
		(s, r) = map(int, input().split())
		if s <= x:
			if r > res:
				res = r
	else:
		print(res)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	m = 0
	for i in range(n):
		(s, r) = map(int, input().split())
		if s <= x:
			if r > m:
				ans = r
				m = r
	print(ans)


t = int(input())
for i in range(t):
	(a, b) = map(int, input().split())
	m = 0
	for i in range(a):
		(s, r) = map(int, input().split())
		if s > b:
			pass
		elif r > m:
			m = r
	print(m)


t = int(input())
while t != 0:
	(n, x) = map(int, input().split())
	size = []
	rating = []
	imdb = []
	for i in range(n):
		(s, y) = map(int, input().split())
		size.append(s)
		rating.append(y)
	for z in range(n):
		if size[z] <= x:
			imdb.append(rating[z])
	print(max(imdb))
	t -= 1


for _ in range(int(input())):
	(movies, spaceleft) = map(int, input().split())
	maxrat = 0
	for i in range(movies):
		(spacereq, rating) = map(int, input().split())
		if spacereq <= spaceleft:
			if rating > maxrat:
				maxrat = rating
	print(maxrat)


for i in range(int(input())):
	(a, b) = map(int, input().split())
	large = 0
	for i in range(a):
		(c, d) = map(int, input().split())
		if c <= b:
			if d > large:
				large = d
	print(large)


for _ in range(int(input())):
	(n, x) = map(int, input().split())
	l = []
	for i in range(n):
		(a, b) = map(int, input().split())
		if a <= x:
			l.append(b)
		else:
			pass
	print(max(l))


for _ in range(int(input())):
	(no, space) = map(int, input().split())
	max_rating = 0
	for i in range(no):
		(size, rat) = map(int, input().split())
		if size <= space and rat > max_rating:
			max_rating = rat
	print(max_rating)


for i in range(int(input())):
	(n, x) = map(int, input().split())
	s = []
	r = []
	ans = 0
	for i in range(n):
		(a, b) = map(int, input().split())
		s.append(a)
		r.append(b)
	for k in range(n):
		if s[k] <= x:
			if ans < r[k]:
				ans = r[k]
	print(ans)


T = int(input())
while T > 0:
	(N, X) = map(int, input().split())
	initial = 0
	answer = 0
	for i in range(N):
		(S, R) = map(int, input().split())
		if S <= X:
			if R > initial:
				answer = R
				initial = R
	print(answer)
	T -= 1


t = int(input())
for i in range(t):
	dict = {}
	(n, x) = map(int, input().split())
	for i in range(n):
		(s, r) = map(int, input().split())
		if s <= x:
			dict[r] = s
	max_r = max(dict.keys())
	print(max_r)