Read problems statements in [Hindi], [Mandarin Chinese], [Russian], [Vietnamese], and [Bengali] as well.

Chef went to the store in order to buy one can of coke. In the store, they offer $N$ cans of coke (numbered $1$ through $N$). For each valid $i$, the current temperature of the $i$-th can is $C_{i}$ and its price is $P_{i}$.

After buying a can of coke, Chef wants to immediately start walking home; when he arrives, he wants to immediately drink the whole can. It takes Chef $M$ minutes to get home from the store.

The ambient temperature outside is $K$. When a can of coke is outside, its temperature approaches the ambient temperature. Specifically, if its temperature is $t$ at some point in time:
if $t > K+1$, then one minute later, its temperature will be $t-1$
if $t < K-1$, then one minute later, its temperature will be $t+1$
if $K-1 ≤ t ≤ K+1$, then one minute later, its temperature will be $K$

When Chef drinks coke from a can, he wants its temperature to be between $L$ and $R$ (inclusive). Find the cheapest can for which this condition is satisfied or determine that there is no such can.

------  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 five space-separated integers $N$, $M$, $K$, $L$ and $R$.
$N$ lines follow. For each $i$ ($1 ≤ i ≤ N$), the $i$-th of these lines contains two space-separated integers $C_{i}$ and $P_{i}$.

------  Output ------
For each test case, print a single line containing one integer — the price of the can Chef should buy, or $-1$ if it is impossible to buy a can such that Chef's condition is satisfied.

------  Constraints  ------
$1 ≤ T ≤ 1,000$
$1 ≤ N ≤ 100$
$1 ≤ M ≤ 100$
$|C_{i}| ≤ 50$ for each valid $i$
$|K| ≤ 50$
$-50 ≤ L ≤ R ≤ 50$
$1 ≤ P_{i} ≤ 10^{6}$ for each valid $i$

----- Sample Input 1 ------ 
2
3 2 5 4 6
1 6
2 8
8 10
3 5 10 20 30
21 20
22 22
23 23
----- Sample Output 1 ------ 
8
-1
----- explanation 1 ------ 
Example case 1: Chef should buy the second can (with price $8$), even though the first can is cheaper. If Chef bought the first can, its temperature would be $3$ when he got home, and that is outside the range $[4, 6]$.

Example case 2: No matter which can Chef buys, when he gets home, its temperature will be less than $20$, so there is no suitable can available in the store.

Difficulty: MEDIUM
Tags: Mathematics

Starter code:

Solutions:
t = int(input())
for i in range(t):
	(cans, minutes, outsidet, le, ri) = map(int, input().split())
	ans = -1
	for i in range(cans):
		(x, y) = map(int, input().split())
		for i in range(minutes):
			if x > outsidet + 1:
				x = x - 1
			elif x < outsidet - 1:
				x = x + 1
			else:
				x = outsidet
		if x >= le and x <= ri:
			if ans == -1:
				ans = y
			elif ans > y:
				ans = y
	print(ans)


t = int(input())
for i in range(t):
	(n, m, k, l, r) = list(map(int, input().split()))
	cheapest = -1
	for j in range(n):
		(c, p) = list(map(int, input().split()))
		for q in range(m):
			if c > k + 1:
				c = c - 1
			elif c < k - 1:
				c = c + 1
			elif k - 1 <= c <= k + 1:
				c = k
		if l <= c <= r:
			if cheapest == -1:
				cheapest = p
			elif cheapest > p:
				cheapest = p
	print(cheapest)


t = int(input())
while t > 0:
	(n, m, k, l, r) = map(int, input().split())
	s = []
	for i in range(0, n):
		(c, p) = map(int, input().split())
		if abs(k - c) <= m:
			temp = k
		elif c < k - 1:
			temp = c + m
		else:
			temp = c - m
		if l <= temp and temp <= r:
			s.append(p)
	if len(s) == 0:
		print('-1')
	else:
		print(min(s))
	t = t - 1


t = int(input())
for x in range(t):
	(n, m, k, l, r) = [int(i) for i in input().split()]
	min = 10000000
	for i in range(n):
		(c, p) = [int(a) for a in input().split()]
		for j in range(m):
			if c > k + 1:
				c = c - 1
			elif c < k - 1:
				c = c + 1
			elif c >= k - 1 and c <= k + 1:
				c = k
		if l <= c and c <= r:
			if min > p:
				min = p
	if min == 10000000:
		print(-1)
	else:
		print(min)


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, m, k, l, r) = map(int, input().split())
	(c, p) = ([], [])
	for i in range(n):
		(ci, pi) = map(int, input().split())
		c.append(ci)
		p.append(pi)
	while m:
		for i in range(len(c)):
			if c[i] > k + 1:
				c[i] = c[i] - 1
			elif c[i] < k - 1:
				c[i] = c[i] + 1
			elif k - 1 <= c[i] <= k + 1:
				c[i] = k
		m -= 1
	ans = []
	for i in range(len(c)):
		if l <= c[i] <= r:
			ans.append(p[i])
	if ans:
		print(min(ans))
	else:
		print(-1)


t = int(input())
for i in range(t):
	(n, m, k, l, r) = [int(x) for x in input().split()]
	x = []
	y = []
	for i in range(n):
		(c, p) = [int(x) for x in input().split()]
		x.append(c)
		y.append(p)
	while m:
		for i in range(len(x)):
			if x[i] > k + 1:
				x[i] = x[i] - 1
			elif x[i] < k - 1:
				x[i] = x[i] + 1
			elif k - 1 <= x[i] <= k + 1:
				x[i] = k
		m -= 1
	k = []
	for i in range(len(x)):
		if l <= x[i] <= r:
			k.append(y[i])
	if k:
		print(min(k))
	else:
		print(-1)


t = int(input())
for _ in range(t):
	(n, m, k, l, r) = map(int, input().split())
	s = []
	for i in range(n):
		s.append(list(map(int, input().split())))
	ans = 10000000000
	for i in range(n):
		c = s[i][0]
		if abs(c - k) > m:
			if c < k:
				c += m
			else:
				c -= m
		else:
			c = k
		if c >= l and c <= r:
			ans = min(s[i][1], ans)
	if ans == 10000000000:
		ans = -1
	print(ans)


import math
case = int(input())
for _ in range(case):
	(n, m, k, l, r) = map(int, input().split(' '))
	res = math.inf
	for i in range(n):
		(temp, price) = map(int, input().split(' '))
		nt = temp
		if temp > k:
			nt = temp - m
			if nt <= k:
				nt = k
		if temp < k:
			nt = temp + m
			if nt >= k:
				nt = k
		if nt >= l and nt <= r:
			res = min(res, price)
	if res == math.inf:
		print(-1)
	else:
		print(res)


T = int(input())
while T != 0:
	flag = 0
	min = 10 ** 9
	(n, m, k, l, r) = tuple(map(int, input().split()))
	for i in range(n):
		(t, p) = tuple(map(int, input().split()))
		temp = m
		while temp != 0:
			if t > k + 1:
				t -= 1
			elif t < k - 1:
				t += 1
			else:
				t = k
			temp -= 1
		if l <= t <= r and min > p:
			flag = 1
			min = p
	if flag == 0:
		print(-1)
	else:
		print(min)
	T -= 1


for _ in range(int(input())):
	(n, m, k, l, r) = map(int, input().split())
	L = []
	for i in range(n):
		(c, p) = map(int, input().split())
		if c < k:
			c = min(c + m, k)
		else:
			c = max(c - m, k)
		if c in range(l, r + 1):
			L.append(p)
	if L == []:
		print(-1)
	else:
		print(min(L))


for i in range(int(input())):
	(n, m, k, l, r) = map(int, input().split())
	mp = 10000009
	for i in range(n):
		(c, p) = map(int, input().split())
		if c > k:
			t = max(c - m, k)
		else:
			t = min(c + m, k)
		if l <= t <= r:
			mp = min(mp, p)
	if mp == 10000009:
		print(-1)
	else:
		print(mp)


import sys
t = int(input())
for _ in range(t):
	list1 = list(map(int, input().split()))
	list2 = []
	temp = -1
	p = sys.maxsize
	for i in range(list1[0]):
		list3 = list(map(int, input().split()))
		list2.append(list3)
		if list2[i][0] > list1[2]:
			if list2[i][0] - list1[1] > list1[2]:
				if list1[3] <= list2[i][0] - list1[1] <= list1[4]:
					if list2[i][1] < p:
						p = list2[i][1]
			elif list1[3] <= list1[2] <= list1[4]:
				if list2[i][1] < p:
					p = list2[i][1]
		elif list2[i][0] < list1[2]:
			if list2[i][0] + list1[1] < list1[2]:
				if list1[3] <= list2[i][0] + list1[1] <= list1[4]:
					if list2[i][1] < p:
						p = list2[i][1]
			elif list1[3] <= list1[2] <= list1[4]:
				if list2[i][1] < p:
					p = list2[i][1]
		elif list1[3] <= list1[2] <= list1[4]:
			if list2[i][1] < p:
				p = list2[i][1]
	if p == sys.maxsize:
		p = -1
	print(p)


import sys
from sys import stdin
stdint = lambda : int(stdin.readline())
mul = lambda : map(int, stdin.readline().strip().split())
for _ in range(stdint()):
	(n, m, k, l, r) = mul()
	minPrice = sys.maxsize
	for i in range(n):
		(c, p) = mul()
		if c > k:
			t = max(c - m, k)
		else:
			t = min(c + m, k)
		if l <= t <= r:
			minPrice = min(minPrice, p)
	if minPrice == sys.maxsize:
		print(-1)
	else:
		print(minPrice)


for _ in range(int(input())):
	(N, M, K, L, R) = map(int, input().split())
	chosen = -1
	for i in range(N):
		(c, p) = map(int, input().split())
		if c < K and c + M < K:
			t = c + M
		elif c > K and c - M > K:
			t = c - M
		else:
			t = K
		if L <= t <= R and (p < chosen or chosen == -1):
			chosen = p
	print(chosen)


for _ in range(int(input())):
	final = []
	(n, m, k, l, r) = map(int, input().split())
	for i in range(n):
		(c, p) = map(int, input().split())
		for j in range(m):
			if c > k + 1:
				c -= 1
			elif c < k - 1:
				c += 1
			elif c >= k - 1 and c <= k + 1:
				c = k
		if c >= l and c <= r:
			final.append(p)
	if final == []:
		print(-1)
	else:
		print(min(final))


for _ in range(int(input())):
	(N, M, K, L, R) = map(int, input().split())
	l = []
	for i in range(N):
		l.append(list(map(int, input().split())))
	tlist = []
	for i in range(N):
		if K >= l[i][0]:
			if K <= l[i][0] + M:
				l[i][0] = K
			else:
				l[i][0] = l[i][0] + M
			if L <= l[i][0] <= R:
				tlist.append([i + 1, l[i][1]])
		elif K < l[i][0]:
			if K >= l[i][0] - M:
				l[i][0] = K
			else:
				l[i][0] = l[i][0] - M
			if L <= l[i][0] <= R:
				tlist.append([i + 1, l[i][1]])
	if len(tlist) == 0:
		print(-1)
	else:
		min = tlist[0][1]
		for i in range(len(tlist)):
			if tlist[i][1] < min:
				min = tlist[i][1]
		print(min)


satya = int(input())
for ti in range(satya):
	(sai, md, kd, ld, rd) = map(int, input().split(' '))
	prd = -1
	for i in range(sai):
		(cd, pd) = map(int, input().split(' '))
		if cd < kd:
			final_temp = min(cd + md, kd)
		else:
			final_temp = max(cd - md, kd)
		if ld <= final_temp and final_temp <= rd:
			if prd != -1:
				prd = min(pd, prd)
			else:
				prd = pd
	print(prd)


t = int(input())
for ti in range(t):
	(n, m, k, l, r) = map(int, input().split(' '))
	price = -1
	for i in range(n):
		(c, p) = map(int, input().split(' '))
		if c < k:
			final_temp = min(c + m, k)
		else:
			final_temp = max(c - m, k)
		if l <= final_temp and final_temp <= r:
			if price != -1:
				price = min(p, price)
			else:
				price = p
	print(price)


for _ in range(int(input())):
	(N, M, K, L, R) = map(int, input().split())
	list_cans = []
	for can in range(N):
		(temp, price) = map(int, input().split())
		ans = -1
		for minute in range(M):
			if temp > K:
				temp -= 1
			elif temp < K:
				temp += 1
			else:
				temp = K
		if L <= temp <= R:
			ans = price
		list_cans.append(ans)
	if list_cans.count(-1) == len(list_cans):
		print(-1)
	else:
		for can in range(list_cans.count(-1)):
			list_cans.remove(-1)
		print(min(list_cans))


T = int(input())
for _ in range(T):
	(N, M, K, L, R) = map(int, input().split(' '))
	price = []
	for _ in range(N):
		(C, P) = map(int, input().split())
		temp = C
		for i in range(M):
			if temp > K + 1:
				temp = temp - 1
			elif temp < K - 1:
				temp = temp + 1
			elif temp >= K - 1 and temp <= K + 1:
				temp = K
		if temp >= L and temp <= R:
			price.append(P)
	if len(price) == 0:
		print(-1)
	else:
		print(min(price))


t = int(input())
for _ in range(t):
	(n, m, k, l, r) = map(int, input().split())
	price = []
	for _ in range(n):
		(c, p) = map(int, input().split())
		temp = c
		for i in range(m):
			if temp > k + 1:
				temp = temp - 1
			elif temp < k - 1:
				temp = temp + 1
			elif temp >= k - 1 and temp <= k + 1:
				temp = k
		if temp >= l and temp <= r:
			price.append(p)
	if len(price) == 0:
		print(-1)
	else:
		print(min(price))


for _ in range(int(input())):
	(n, m, k, l, r) = map(int, input().split())
	valid = []
	for i in range(n):
		(c, p) = map(int, input().split())
		if c < k:
			c += min(k - c, m)
		elif c > k:
			c -= min(c - k, m)
		if l <= c <= r:
			valid.append(p)
	if len(valid) == 0:
		print(-1)
	else:
		print(min(valid))


T = int(input())
for _ in range(T):
	(N, M, K, L, R) = map(int, input().split())
	(max_P, result) = (1000000, -1)
	for _ in range(N):
		(C, P) = map(int, input().split())
		for _ in range(M):
			if C < K - 1:
				C += 1
			elif C > K + 1:
				C -= 1
			elif K - 1 <= C and C <= K + 1:
				C = K
		if L <= C and C <= R:
			if P <= max_P:
				(max_P, result) = (P, P)
	print(result)


def helper_function(ambient_temp, coke_temp, minutes, range_low, range_high):
	if coke_temp >= ambient_temp:
		final_temp = max(coke_temp - minutes, ambient_temp)
	else:
		final_temp = min(coke_temp + minutes, ambient_temp)
	return final_temp >= range_low and final_temp <= range_high

def solver(m, k, l, r, list_of_temperatures_and_prices):
	list_of_temperatures_and_prices.sort(key=lambda x: x[1])
	for sub_list in list_of_temperatures_and_prices:
		if helper_function(k, sub_list[0], m, l, r):
			return sub_list[1]
	return -1
t = int(input())
for i in range(t):
	(n, m, k, l, r) = map(int, input().split())
	list_of_temperatures_and_prices = []
	for j in range(n):
		(c, p) = map(int, input().split())
		list_of_temperatures_and_prices.append([c, p])
	print(solver(m, k, l, r, list_of_temperatures_and_prices))


def reach_ambient(c):
	for _ in range(m):
		if c > k:
			c -= 1
		elif c < k:
			c += 1
		elif c == k:
			break
	return c
for _ in range(int(input())):
	(n, m, k, l, r) = map(int, input().split())
	prices = []
	for _ in range(n):
		(c, p) = map(int, input().split())
		ft = reach_ambient(c)
		if ft >= l and ft <= r:
			prices.append(p)
	if len(prices) == 0:
		print(-1)
	else:
		print(min(prices))


def chefDrinksCoke():
	for i in range(int(input())):
		tstInput = [int(x) for x in input().split()]
		n = tstInput[0]
		m = tstInput[1]
		k = tstInput[2]
		l = tstInput[3]
		r = tstInput[4]
		minCost = -1
		for j in range(n):
			canInfo = [int(x) for x in input().split()]
			temp = canInfo[0]
			cost = canInfo[1]
			tempDif = temp - k
			if m >= abs(tempDif):
				temp = k
			elif tempDif < 0:
				temp += m
			elif tempDif > 0:
				temp -= m
			if temp <= r and temp >= l:
				if minCost > 0 and cost < minCost:
					minCost = cost
				elif minCost < 0 and cost > 0:
					minCost = cost
		print(minCost)
chefDrinksCoke()


tests = int(input())
for i in range(tests):
	(n, m, k, l, r) = map(int, input().split())
	ans_price = 10 ** 6 + 1
	for _ in range(n):
		(c, p) = map(int, input().split())
		if c < k:
			last_temp = min(k, c + m)
			if l <= last_temp <= r and p < ans_price:
				ans_price = p
		else:
			last_temp = max(k, c - m)
			if l <= last_temp <= r and p < ans_price:
				ans_price = p
	if ans_price == 10 ** 6 + 1:
		ans_price = -1
	print(ans_price)


for _ in range(int(input())):
	(n, m, k, l, r) = map(int, input().split())
	X = []
	for tc in range(n):
		(c, p) = map(int, input().split())
		t = m
		while t > 0:
			if c < k - 1:
				c += 1
			elif c > k + 1:
				c -= 1
			else:
				c = k
			t -= 1
		if c >= l and c <= r:
			X.append(p)
	if len(X) > 0:
		print(min(X))
	else:
		print(-1)


for _ in range(int(input())):
	arr = []
	res = []
	(n, m, k, l, r) = map(int, input().split())
	for _ in range(n):
		arr.append(list(map(int, input().split())))
	for i in arr:
		for j in range(m):
			if i[0] < k - 1:
				i[0] += 1
			elif i[0] > k + 1:
				i[0] -= 1
			elif i[0] <= k + 1 and i[0] >= k - 1:
				i[0] = k
		if i[0] >= l and i[0] <= r:
			res.append(i[1])
	if res:
		print(min(res))
	else:
		print(-1)


q = int(input())
for lo in range(q):
	(n, m, k, l, r) = map(int, input().split())
	c = []
	p = []
	t1 = 0
	for g in range(n):
		(x, y) = map(int, input().split())
		c.append(x)
		p.append(y)
	len_p = len(p)
	flag = 0
	ans = []
	for i in range(len_p):
		t = 0
		t1 = c[i]
		t2 = p[i]
		t = t1
		for j in range(1, m + 1):
			if t < k - 1:
				t += 1
			elif t < k + 1:
				t = k
			else:
				t -= 1
		if l <= t <= r:
			ans.append(t2)
	r1 = len(ans)
	if r1 == 0:
		print(-1)
	else:
		print(min(ans))


t = int(input())
for index in range(t):
	data = list(map(int, input().split()))
	n = data[0]
	m = data[1]
	k = data[2]
	l = data[3]
	r = data[4]
	c = []
	p = []
	for i in range(n):
		data2 = list(map(int, input().split()))
		c.append(data2[0])
		p.append(data2[1])
	ls_fine = []
	for i in range(n):
		t = c[i]
		m = data[1]
		while m > 0:
			if t < k - 1:
				t += 1
			elif t < k + 1:
				t = k
			else:
				t -= 1
			m -= 1
		if l <= t and t <= r:
			ls_fine.append(p[i])
	if len(ls_fine) == 0:
		print(-1)
	else:
		print(min(ls_fine))


import math
for _ in range(int(input())):
	n = list(map(int, input().strip().split()))
	ans = []
	for i in range(n[0]):
		a = list(map(int, input().strip().split()))
		if a[0] > n[2]:
			if a[0] - n[1] <= n[2]:
				a[0] = n[2]
			else:
				a[0] -= n[1]
		elif a[0] < n[2]:
			if a[0] + n[1] >= n[2]:
				a[0] = n[2]
			else:
				a[0] += n[1]
		if a[0] >= n[3] and a[0] <= n[4]:
			ans.append(a[1])
	ans.sort()
	if len(ans) == 0:
		print(-1)
	else:
		print(ans[0])


from bisect import bisect_left
from code import interact
from heapq import heapify, heappush, heappop
from collections import deque
from pydoc import plain
from re import X
import sys
from math import gcd, sqrt, log10, log2, floor, ceil, sqrt
input = sys.stdin.readline

def il():
	return [int(a) for a in input().strip().split()]

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

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

def ot(in_p, *args, e=' '):
	if type(in_p) == list:
		print(*in_p, end=e)
	if type(in_p) == str or type(in_p) == int:
		print(in_p, end=e)
		for l in args:
			print(l, end=e)
	print()

def a_pwr_n(a, n, mod):
	if n == 1:
		return a % mod
	if n % 2 == 0:
		val = a_pwr_n(a, n // 2, mod)
		return val % mod * val % mod
	else:
		return a % mod * a_pwr_n(a, n - 1, mod) % mod

def rg(*ag):
	if len(ag) == 3:
		return range(ag[0], ag[1], ag[2])
	elif len(ag) == 2:
		return range(ag[0], ag[1])
	elif len(ag) == 1:
		return range(ag[0])
	else:
		raise 'invalid input'

def ispal(i, j, st):
	while i <= j:
		if st[i] == st[j]:
			i = i + 1
			j = j - 1
		else:
			return False
	return True
mod = 1000000000 + 7
dx = [-1, -2, 1, 2, 2, -2, -1, 1]
dy = [2, 1, 2, 1, -1, -1, -2, -2]
for _ in range(ii()):
	(n, m, k, l, r) = il()
	c = []
	p = []
	minp = 1000001
	for _ in range(n):
		ip = il()
		c.append(ip[0])
		p.append(ip[1])
	for i in range(n):
		t = c[i]
		for j in range(m):
			if t > k + 1:
				t -= 1
			elif t < k - 1:
				t += 1
			elif t >= k - 1 and t <= k + 1:
				t = k
		if t >= l and t <= r:
			if p[i] < minp:
				minp = p[i]
	if minp == 1000001:
		print('-1')
	else:
		print(minp)


for _ in range(int(input())):
	(n, m, k, l, r) = map(int, input().split())
	cokes = []
	for i in range(n):
		(ci, pi) = map(int, input().split())
		cokes.append([ci, pi])
	cokes.sort(key=lambda x: x[1])
	for i in range(n):
		if cokes[i][0] <= k:
			ans = min(cokes[i][0] + m, k)
			if l <= ans <= r:
				print(cokes[i][1])
				break
		else:
			ans = max(cokes[i][0] - m, k)
			if l <= ans <= r:
				print(cokes[i][1])
				break
	else:
		print(-1)


from math import gcd, sqrt, ceil, floor, log10, log2
from heapq import heapify, heappop, heappush, nsmallest, nlargest
from collections import Counter, deque, OrderedDict, defaultdict
from itertools import combinations, permutations, zip_longest
from bisect import bisect_left, bisect_right
from functools import lru_cache, reduce
import sys
import time
import string
import operator
RECURSION_LIMIT = int(10000000.0)
INT_MAX = float('inf')
INT_MIN = float('-inf')
MOD = int(10000000.0) + 9
NEWLINE = '\n'
SPACE = ' '
sys.setrecursionlimit(RECURSION_LIMIT)
inp = lambda fn: fn(input())
inp_vars = lambda fn, delim, convert_to=list: convert_to(map(fn, input().split(delim)))
enum = lambda itr: enumerate(itr)

def toposort(graph, n):
	degree = [0] * n
	for node in graph:
		for adj in graph[node]:
			degree[adj] += 1
	bfs_queue = [node for node in range(n) if not degree[node]]
	for node in bfs_queue:
		for adj in graph[node]:
			degree[adj] -= 1
			if not degree[adj]:
				bfs_queue.append(adj)
	return (bfs_queue, degree)

def dfs(graph, node, visited):
	visited.add(node)
	for adj in graph[node]:
		if adj in visited:
			continue
		dfs(graph, adj, visited)

def seive(n):
	is_prime = [True] * (n + 1)
	is_prime[0] = is_prime[1] = False
	for i in range(2, int(n ** 0.5) + 1):
		if is_prime[i]:
			for j in range(i * i, n + 1, i):
				is_prime[j] = False
	return is_prime[n]

def solve(*args, **kwargs):
	(n, m, k, l, r, arr) = args
	res = INT_MAX
	for (temp, price) in arr:
		if temp < k - 1:
			temp = min(temp + m, k)
		elif temp > k + 1:
			temp = max(temp - m, k)
		else:
			temp = k
		if l <= temp <= r and res > price:
			res = price
	return res if res != INT_MAX else -1

def main(*args, **kwargs):
	for _ in range(int(input())):
		arg1 = inp_vars(int, SPACE)
		arg3 = [inp_vars(int, SPACE) for _ in range(arg1[0])]
		res = solve(*(*arg1, arg3))
		if type(res) in {list, tuple, set}:
			print(*res, sep='\n')
		else:
			print(res)
main()


def fn(l):
	return l[1]
for _ in range(int(input())):
	(n, m, k, l, r) = map(int, input().split())
	lst = []
	for i in range(n):
		lst.append(list(map(int, input().split())))
	for i in range(m):
		for j in lst:
			if j[0] < k:
				j[0] += 1
			if j[0] > k:
				j[0] -= 1
	ans = []
	for i in lst:
		if r >= i[0] >= l:
			ans.append(i)
	if not ans:
		print(-1)
	else:
		print(min(ans, key=fn)[1])


T = int(input())
for i in range(0, T):
	a = input().split()
	for j in range(0, 5):
		a[j] = int(a[j])
	tem = []
	pric = []
	for j in range(0, a[0]):
		(aa, b) = input().split()
		tem.append(int(aa))
		pric.append(int(b))
	for j in range(0, a[0]):
		count = 0
		c = tem[j]
		while count < a[1] and c < a[2]:
			c += 1
			count += 1
		while count < a[1] and c > a[2]:
			c -= 1
			count += 1
		tem[j] = c
	c = []
	for j in range(0, a[0]):
		if tem[j] <= a[4] and tem[j] >= a[3]:
			c.append(pric[j])
	a = len(c)
	if a == 0:
		print(-1)
	else:
		pric = c[0]
		for j in c:
			pric = min(pric, j)
		print(pric)


from math import inf

def solve():
	(n, m, k, l, r) = map(int, input().split())
	ans = inf
	for i in range(n):
		(c, p) = map(int, input().split())
		if k - 1 <= c <= k + 1:
			if l <= k <= r:
				ans = min(ans, p)
		elif c < k - 1:
			extra = k - 1 - c
			if m > extra:
				if l <= k <= r:
					ans = min(ans, p)
			else:
				c = c + m
				if l <= c <= r:
					ans = min(ans, p)
		else:
			extra = c - k - 1
			if m > extra:
				if l <= k <= r:
					ans = min(ans, p)
			else:
				c = c - m
				if l <= c <= r:
					ans = min(ans, p)
	print(ans if ans != inf else -1)
for _ in range(int(input())):
	solve()


t = int(input())
while t > 0:
	t -= 1
	(n, m, k, l, r) = map(int, input().split())
	c = [0] * n
	p = [0] * n
	x = []
	for i in range(n):
		(c[i], p[i]) = map(int, input().split())
		for j in range(m):
			if c[i] > k + 1:
				c[i] -= 1
			elif c[i] < k - 1:
				c[i] += 1
			elif c[i] <= k + 1 and c[i] >= k - 1:
				c[i] = k
		if c[i] >= l and c[i] <= r:
			x.append(p[i])
	if x == []:
		print(-1)
	else:
		print(min(x))


for _ in range(int(input())):
	(n, m, k, l, r) = map(int, input().split())
	answer = -1
	for _ in range(n):
		(c, p) = map(int, input().split())
		final_temp = min(k, c + m)
		if c > k:
			final_temp = max(k, c - m)
		req_temp = range(l, r + 1)
		if final_temp in req_temp and (p < answer or answer == -1):
			answer = p
	print(answer)


for _ in range(int(input())):
	(n, m, k, l, r) = map(int, input().split())
	answer = -1
	for _ in range(n):
		temp_m = m
		(c, p) = map(int, input().split())
		while temp_m != 0:
			if c > k + 1:
				c -= 1
			elif c < k - 1:
				c += 1
			else:
				c = k
				break
			temp_m -= 1
		req_temp = range(l, r + 1)
		if c in req_temp and (p < answer or answer == -1):
			answer = p
	print(answer)


def temp(t, K, M):
	for i in range(M):
		if t > K + 1:
			t = t - 1
		elif t < K - 1:
			t = t + 1
		else:
			t = K
	return t
T = int(input())
for i in range(T):
	(N, M, K, L, R) = map(int, input().split())
	lst = []
	for j in range(N):
		(C, P) = map(int, input().split())
		if temp(C, K, M) >= L and temp(C, K, M) <= R:
			lst.append(P)
	if lst == []:
		print(-1)
	else:
		print(min(lst))


tc = int(input())
while tc > 0:
	ntc_p = input()
	listt = list(map(int, ntc_p.split()))
	(n, m, k, l, r) = (listt[0], listt[1], listt[2], listt[3], listt[4])
	(c, p, q) = ([], [], [])
	while n > 0:
		ntc_v = input()
		listt_v = list(map(int, ntc_v.split()))
		c.append(listt_v[0])
		p.append(listt_v[1])
		n -= 1
	(i, e, n) = (0, 0, listt[0])
	while i < n:
		if c[i] > k + 1:
			c[i] -= 1
		elif c[i] < k - 1:
			c[i] += 1
		else:
			c[i] = k
		i += 1
		if e < m - 1:
			e += 1
			i -= 1
		else:
			if c[i - 1] >= l and c[i - 1] <= r:
				q.append(p[i - 1])
			e = 0
	if q == []:
		print('-1')
	else:
		print(min(q))
	tc -= 1


def solve():
	(n, m, k, l, r) = list(map(int, input().split()))
	ans = float('inf')
	for i in range(n):
		(c, p) = list(map(int, input().split()))
		if c < k:
			c += m
			if c > k:
				c = k
		elif c > k:
			c -= m
			if c < k:
				c = k
		if l <= c and c <= r:
			ans = min(ans, p)
	if ans == float('inf'):
		return -1
	return ans
tc = int(input())
for t in range(tc):
	print(solve())


t = int(input())
for j in range(t):
	(n, m, k, l, r) = map(int, input().split())
	d = []
	for i in range(n):
		(c, p) = map(int, input().split())
		if c >= k:
			c -= m
			if c < k:
				c = k
		else:
			c += m
			if c > k:
				c = k
		if c in range(l, r + 1):
			d.append(p)
	if len(d) == 0:
		print(-1)
	else:
		print(min(d))


for _ in range(int(input())):
	(n, m, k, l, r) = map(int, input().split())
	q = []
	for i in range(n):
		(c, p) = map(int, input().split())
		for j in range(m):
			if c < k - 1:
				c += 1
			elif c > k + 1:
				c -= 1
			elif c <= k + 1 and c >= k - 1:
				c = k
				break
		if c >= l and c <= r:
			q.append(p)
	if len(q) == 0:
		print(-1)
	else:
		print(min(q))


for _ in range(int(input())):
	(n, m, k, l, r) = [int(x) for x in input().strip().split()]
	ratures = []
	prices = []
	for _ in range(n):
		(c, p) = [int(x) for x in input().strip().split()]
		ratures.append(c)
		prices.append(p)
	res = []
	for i in range(len(ratures)):
		check = ratures[i]
		for j in range(m, 0, -1):
			if check > k + 1:
				check -= 1
			elif check < k - 1:
				check += 1
			elif check >= k - 1 and check <= k + 1:
				check = k
			else:
				continue
		if check >= l and check <= r:
			res.append(prices[i])
	if len(res) == 0:
		print(-1, end='\n')
	else:
		ans = min(res)
		print(ans, end='\n')


t = int(input())
for _ in range(t):
	(n, m, k, l, r) = [int(x) for x in input().split()]
	prices = []
	for i in range(n):
		(t, cost) = [int(p) for p in input().split()]
		for j in range(m, 0, -1):
			if t > k + 1:
				t -= 1
			elif t < k - 1:
				t += 1
			elif t >= k - 1 and t <= k + 1:
				t = k
			else:
				continue
		if l <= t and t <= r:
			prices.append(cost)
	if prices:
		print(min(prices))
	else:
		print(-1)


for i in range(int(input())):
	(n, m, k, l, r) = map(int, input().split())
	cost = None
	for j in range(n):
		(c, p) = map(int, input().split())
		if cost is None or p < cost:
			if c < k:
				x = k - c
				if m >= x:
					temp = k
				else:
					temp = c + m
			elif c == k:
				temp = k
			else:
				x = c - k
				if m >= x:
					temp = k
				else:
					temp = c - m
			if temp >= l and temp <= r:
				cost = p
	if cost is None:
		print(-1)
	else:
		print(cost)


for _ in range(int(input())):
	(n, m, k, l, r) = map(int, input().split())
	z = []
	for j in range(n):
		(x, y) = map(int, input().split())
		for j in range(m):
			if x > k + 1:
				x -= 1
			elif x < k - 1:
				x += 1
			else:
				x = k
		if l <= x <= r:
			z.append(y)
	if len(z) == 0:
		print(-1)
	else:
		print(min(z))


for i in range(int(input())):
	(n, m, k, l, r) = map(int, input().split())
	l1 = []
	for i in range(n):
		(p, q) = map(int, input().split())
		temp = p
		for i in range(m):
			if temp > k + 1:
				temp = temp - 1
			elif temp < k - 1:
				temp = temp + 1
			elif temp >= k - 1 and temp <= k + 1:
				temp = k
		if temp >= l and temp <= r:
			l1.append(q)
	if len(l1) == 0:
		print(-1)
	else:
		print(min(l1))


for i in range(int(input())):
	costs = []
	(n, m, k, l, r) = map(int, input().split())
	j = 0
	while j < n:
		(c, p) = map(int, input().split())
		mi = 0
		while mi < m:
			if c < k - 1:
				c += 1
			elif c > k + 1:
				c -= 1
			else:
				c = k
			mi += 1
		if l <= c <= r:
			costs.append(p)
		j += 1
	if len(costs) != 0:
		print(min(costs))
	else:
		print(-1)


t1 = int(input())
for _ in range(t1):
	(n, m, k, l, r) = map(int, input().split())
	lci = []
	lpi = []
	for i in range(n):
		(x, y) = map(int, input().split())
		lci.append(x)
		lpi.append(y)
	l_result = []
	for i in range(len(lci)):
		m1 = m
		t = lci[i]
		if t < k - 1:
			while t != k - 1 and m1 > 0:
				t = t + 1
				m1 = m1 - 1
		if t > k + 1:
			while t != k + 1 and m1 > 0:
				t = t - 1
				m1 = m1 - 1
		if t >= k - 1 and t <= k + 1:
			while m1 > 0:
				t = k
				m1 = m1 - 1
		if m1 == 0 and t >= l and (t <= r):
			l_result.append(lpi[i])
	l_result.sort()
	if len(l_result) == 0:
		print(-1)
	else:
		print(l_result[0])