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

Hasan has recently heard about Chef's restaurant, which serves the tastiest dishes. The restaurant has published a list of $N$ dishes (numbered $1$ through $N$) that will be served in the next $M$ days. For each valid $i$, the $i$-th dish will be served only on the $D_{i}$-th day. Hasan has investigated their tastiness and he knows that for each valid $i$, the $i$-th dish has tastiness $V_{i}$.

Hasan's budget is only large enough to try two dishes. He wants to choose these two dishes in such a way that their total (summed up) tastiness is as large as possible. However, he cannot try 2 dishes on the same day.

Help Hasan and calculate the maximum possible total tastiness of the dishes he should try.

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

------  Output ------
For each test case, print a single line containing one integer — the maximum total tastiness.

------  Constraints  ------
$1 ≤ T ≤ 1,000$
$2 ≤ N, M ≤ 10^{5}$
$1 ≤ D_{i} ≤ M$ for each valid $i$
$1 ≤ V_{i} ≤ 10^{9}$ for each valid $i$
there are at least two dishes that are served on different days
the sum of $N$ over all test cases does not exceed $10^{6}$
the sum of $M$ over all test cases does not exceed $10^{6}$

----- Sample Input 1 ------ 
2
3 6
5 7
1 9
2 5
3 7
5 8
2 5
5 10
----- Sample Output 1 ------ 
16
15
----- explanation 1 ------ 
Example case 1: The optimal solution is to try dishes $1$ and $2$.

Example case 2: The optimal solution is to try dishes $2$ and $3$.

Source: codechef | Difficulty: EASY
Tags: Implementation

Greedy algorithms


Solutions:
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	f = s = fv = sv = 0
	for i in range(n):
		(d, v) = map(int, input().split())
		if d in [f, s]:
			if d == f:
				fv = max(fv, v)
			else:
				sv = max(sv, v)
				if sv > fv:
					(f, fv, s, sv) = (s, sv, f, fv)
		elif v >= fv:
			(f, s) = (d, f)
			(fv, sv) = (v, fv)
		elif v > sv:
			sv = v
			s = d
	print(sv + fv)


i = int(input())
re = []
for _ in range(i):
	k = input().split()
	imp = []
	for ele in range(int(k[0])):
		imp.append(input().split())
	dic = {}
	for ele in imp:
		if ele[0] in dic.keys():
			if int(ele[1]) < int(dic[ele[0]]):
				continue
		dic[ele[0]] = ele[1]
	fin = []
	for ele in dic.values():
		fin.append(int(ele))
	fin.sort()
	re.append(fin[-1] + fin[-2])
for ele in re:
	print(ele)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = {}
	for f in range(n):
		(a, b) = map(int, input().split())
		d[a] = max(d.get(a, 0), b)
	e = sorted(d.values())
	print(e[-1] + e[-2])


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	Food = dict()
	for j in range(n):
		(d, v) = list(map(int, input().split()))
		if d in Food:
			if Food[d] <= v:
				Food[d] = v
		else:
			Food[d] = v
	Max_food = sorted(list(Food.values()), reverse=1)
	print(Max_food[0] + Max_food[1])


t = int(input())
for t in range(t):
	(n, m) = [int(i) for i in input().split()]
	d = {}
	for j in range(n):
		s = [int(i) for i in input().split()]
		if s[0] in d:
			d[s[0]] = max(s[1], d[s[0]])
		else:
			d[s[0]] = s[1]
	arr = sorted(d.items(), key=lambda x: -x[1])
	print(arr[0][1] + arr[1][1])


for i in range(int(input())):
	(n, m) = map(int, input().split())
	di = {}
	for i in range(n):
		(d, v) = map(int, input().split())
		if d not in di.keys():
			di[d] = v
		else:
			x = di[d]
			di[d] = max(v, x)
	l = []
	for i in di:
		l.append(di[i])
	l.sort()
	print(l[-1] + l[-2])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	day = {}
	for i in range(n):
		(d, t) = map(int, input().split())
		if d not in day:
			day[d] = t
		elif t > day[d]:
			day[d] = t
	taste = sorted(day.values(), reverse=True)
	print(taste[0] + taste[1])


T = int(input())
for _ in range(T):
	(N, M) = map(int, input().split())
	D = {}
	for __ in range(N):
		(d, v) = map(int, input().split())
		if d not in D:
			D[d] = v
		elif v > D[d]:
			D[d] = v
	L = sorted(D.values(), reverse=True)
	print(L[0] + L[1])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = []
	v = []
	for i in range(n):
		(a, b) = map(int, input().split())
		d.append(a)
		v.append(b)
	m = {}
	for i in range(n):
		if d[i] not in m:
			m[d[i]] = v[i]
		elif v[i] > m[d[i]]:
			m[d[i]] = v[i]
	l = list(m.values())
	l.sort(reverse=True)
	s = l[0] + l[1]
	print(s)


T = int(input())
for _ in range(0, T):
	(n, m) = map(int, input().split())
	ld = {}
	for i in range(0, n):
		(d, v) = map(int, input().split())
		if d not in ld:
			ld[d] = v
		elif ld[d] < v:
			ld[d] = v
	l = list(ld.values())
	l = sorted(l)
	print(l[-1] + l[-2])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	x = {}
	for _ in range(n):
		(d, v) = map(int, input().split())
		if d not in x:
			x[d] = v
		elif x[d] > v:
			pass
		else:
			x[d] = v
	l = list(x.values())
	l = sorted(l)
	print(l[-1] + l[-2])


(t, i) = (int(input()), 1)
(j, d) = (1, {})
while i <= t:
	dishesdays = list(map(int, input().split()))
	while j <= dishesdays[0]:
		dv = list(map(int, input().split()))
		if dv[0] not in d.keys():
			d[dv[0]] = dv[1]
		elif d[dv[0]] < dv[1]:
			d[dv[0]] = dv[1]
		j += 1
	li = list(d.values())
	li.sort(reverse=True)
	print(li[0] + li[1])
	j = 1
	d = {}
	i += 1


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = {}
	for i in range(n):
		(day, test) = map(int, input().split())
		if day in d:
			d[day] = max(d[day], test)
		else:
			d[day] = test
	tests = list(d.values())
	tests.sort()
	print(tests[-1] + tests[-2])


def solve(arr, n, m):
	arr.sort(key=lambda x: x[1])
	mp = {}
	for i in range(n):
		mp[arr[i][0]] = arr[i][1]
	res = []
	for val in mp.values():
		res.append(val)
	res.sort()
	return res[-1] + res[-2]
for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		new = [int(x) for x in input().split()]
		arr.append(new)
	print(solve(arr, n, m))


t = int(input())
for k in range(t):
	a = []
	b = []
	(c, d) = map(int, input().split())
	for m in range(c):
		(o, p) = map(int, input().split())
		a.append(o)
		b.append(p)
	e = {}
	for i in a:
		e[i] = []
	for j in range(len(b)):
		e[a[j]].append(b[j])
	f = []
	for l in e:
		f.append(max(e[l]))
	f.sort()
	print(f[len(f) - 1] + f[len(f) - 2])


t = input()
for c in range(0, int(t)):
	(n, m) = map(int, input().split())
	lt = []
	for i in range(n):
		tempL = list(map(int, input().split()))
		lt.append(tempL)
	l = 0
	sl = 0
	d = {}
	for i in lt:
		d[i[0]] = 0
	for i in lt:
		d[i[0]] = max(d[i[0]], i[1])
	lt = list(d.values())
	for i in lt:
		if i > l:
			sl = l
			l = i
		elif i > sl:
			sl = i
	print(l + sl)


t = int(input())
for _ in range(0, t):
	(n, m) = map(int, input().split())
	dct = dict()
	for i in range(n):
		(a, b) = map(int, input().split())
		if a not in dct:
			dct[a] = b
		elif b > dct[a]:
			dct[a] = b
	l = sorted(list(dct.values()))
	sum1 = l[-1] + l[-2]
	print(sum1)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = [0] * n
	v = [0] * n
	for i in range(n):
		(d[i], v[i]) = map(int, input().split())
	f = {}
	for i in range(len(d)):
		if d[i] not in f:
			f[d[i]] = v[i]
		elif f[d[i]] < v[i]:
			f[d[i]] = v[i]
	m = 0
	for i in f:
		if f[i] > m:
			m = f[i]
	sum = m
	for i in f:
		if f[i] == m:
			f[i] = 0
			break
	m = 0
	for i in f:
		if f[i] > m:
			m = f[i]
	print(sum + m)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	(day, taste) = ([], [])
	for i in range(n):
		(a, b) = map(int, input().split())
		day.append(a)
		taste.append(b)
	di = {}
	for i in range(n):
		if day[i] in di:
			if di[day[i]] < taste[i]:
				di[day[i]] = taste[i]
		else:
			di[day[i]] = taste[i]
	final = list(di.values())
	final.sort(reverse=True)
	print(final[0] + final[1])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	dc = {}
	for x in range(n):
		(di, vi) = map(int, input().split())
		if di in dc:
			if vi > dc[di]:
				dc[di] = vi
		else:
			dc[di] = vi
	ls = dc.values()
	ls = sorted(ls, reverse=True)
	print(ls[0] + ls[1])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = {}
	for i in range(n):
		(a, b) = map(int, input().split())
		if a not in d:
			d[a] = b
		elif a in d and d[a] < b:
			d[a] = b
	l = []
	for c in d.values():
		l.append(c)
	l.sort()
	l.reverse()
	print(l[0] + l[1])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	di = {}
	for i in range(n):
		(d, v) = map(int, input().split())
		d = str(d)
		if d not in di:
			di.update({d: v})
		else:
			x = di[d]
			if v > x:
				di.update({d: v})
	y = di.values()
	y = sorted(list(y), reverse=True)
	fi = y[0]
	se = y[1]
	ans = fi + se
	if len(y) < 2:
		ans = fi
	print(ans)


tests = int(input())
for i in range(tests):
	(n, m) = map(int, input().split())
	arr = [0] * m
	max_day = 0
	max_value = 0
	next_max_day = 0
	next_max_value = 0
	for j in range(n):
		(d, v) = map(int, input().split())
		if v >= max_value:
			if d != max_day:
				next_max_day = max_day
				next_max_value = max_value
				max_day = d
				max_value = v
			else:
				max_value = v
		elif v >= next_max_value:
			next_max_day = d
			next_max_value = v
		if max_value < next_max_value:
			(next_max_value, max_value) = (max_value, next_max_value)
			(next_max_day, max_day) = (max_day, next_max_day)
	print(max_value + next_max_value)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	days = {}
	taste = []
	ds = 0
	ts = 0
	for i in range(n):
		(d, t) = map(int, input().split())
		if d in days:
			if t > days[d]:
				days[d] = t
		else:
			days[d] = t
	for i in days:
		taste.append(days[i])
	taste = sorted(taste)
	print(taste[len(taste) - 1] + taste[len(taste) - 2])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	li = [0] * (m + 1)
	sum = 0
	for i in range(n):
		(d, v) = map(int, input().split())
		li[d] = max(li[d], v)
	li.sort()
	sum = li[-1] + li[-2]
	print(sum)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	di = {}
	for i in range(n):
		(d, v) = map(int, input().split())
		if d in di:
			if di[d] < v:
				di[d] = v
		else:
			di[d] = v
	li = []
	for i in di.values():
		li.append(i)
	li.sort()
	print(li[-1] + li[-2])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = {}
	for i in range(n):
		(a, b) = map(int, input().split())
		if a in d:
			if d[a] < b:
				d[a] = b
		else:
			d[a] = b
	l = [i for i in d.values()]
	l.sort()
	print(l[-1] + l[-2])


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	d = {}
	for _ in range(N):
		(D, V) = map(int, input().split())
		if D in d:
			d[D] = max(d[D], V)
		else:
			d[D] = V
	(largest, secondLargest) = (0, 0)
	for i in d:
		if d[i] > largest:
			secondLargest = largest
			largest = d[i]
		elif d[i] > secondLargest:
			secondLargest = d[i]
	print(largest + secondLargest)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	arr = []
	for _ in range(n):
		l = list(map(int, input().split()))
		arr.append(l)
	arr = sorted(arr, key=lambda x: x[1], reverse=True)
	cal = arr[0][1]
	mon = [arr[0][0]]
	tot = arr[0][0]
	count = 1
	for (i, j) in arr[1:]:
		if i not in mon and count < 2:
			cal += j
			count += 1
			if count >= 2:
				break
		mon.append(i)
	print(cal)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for i in range(n):
		arr.append([int(i) for i in input().split()])
	arr.sort(key=lambda x: -x[1])
	sum = arr[0][1]
	for i in range(1, n):
		if arr[i][0] != arr[0][0]:
			sum += arr[i][1]
			break
	print(sum)


T = int(input())

def algo():
	(N, M) = map(int, input().split(' '))
	(a, b) = (0, 0)
	(i, j) = (-1, -1)
	for m in range(N):
		(p, q) = map(int, input().split(' '))
		if q > b:
			if q > a:
				if i != p:
					d = a
					a = q
					b = d
					d = i
					i = p
					j = d
				else:
					a = q
					i = p
			elif i != p:
				b = q
				j = p
	print(a + b)
for i in range(T):
	algo()


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	my = {}
	for i in range(n):
		(d, v) = map(int, input().split())
		if d in my.keys():
			if my[d] < v:
				my[d] = v
		else:
			my[d] = v
	m1 = 0
	m2 = 0
	for i in my.keys():
		if my[i] > m1 and my[i] > m2:
			m2 = m1
			m1 = my[i]
		elif my[i] > m2:
			m2 = my[i]
	print(m1 + m2)


for i in range(int(input())):
	(n, m) = map(int, input().split())
	d = []
	l = [0 for i in range(m + 2)]
	v = []
	for i in range(n):
		(x, y) = map(int, input().split())
		d.append(x)
		if l[x] < y:
			l[x] = y
		v.append(y)
	m = 0
	vm = max(v)
	m += vm
	l.sort()
	print(m + l[-2])


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = {}
	a = 0
	for i in range(n):
		(k, v) = map(int, input().split())
		if k not in d:
			d[k] = v
		elif d[k] < v:
			d[k] = v
	j = 0
	for i in sorted(d.values(), reverse=True):
		a += i
		j += 1
		if j == 2:
			break
	print(a)


import operator
t = int(input())
while t != 0:
	(n, m) = map(int, input().split())
	s = {}
	for i in range(n):
		(di, vi) = map(int, input().split())
		if di in s and s[di] < vi:
			s[di] = vi
		elif di not in s:
			s[di] = vi
	s = sorted(s.items(), key=operator.itemgetter(1), reverse=True)
	print(s[0][1] + s[1][1])
	t -= 1


t = int(input())
for _ in range(t):
	(n, x) = map(int, input().split())
	l1 = [0] * x
	for i in range(n):
		(d, v) = map(int, input().split())
		if l1[d - 1] < v:
			l1[d - 1] = v
	l1.sort()
	print(l1[-1] + l1[-2])


import math
for i in range(int(input())):
	(n, m) = map(int, input().split())
	d = [0 for j in range(m + 2)]
	for j in range(n):
		(day, taste) = map(int, input().split())
		if d[day] < taste:
			d[day] = taste
	d.sort()
	print(d[-1] + d[-2])


t = int(input())
for i in range(t):
	(n, m) = list(map(int, input().split()))
	d = {}
	for j in range(n):
		(p, q) = list(map(int, input().split()))
		if p not in d:
			d[p] = q
		elif d[p] < q:
			d[p] = q
	k = [x for x in d.values()]
	m2 = max(k)
	k.remove(m2)
	m2 += max(k)
	print(m2)


for tc in range(int(input())):
	(N, M) = list(map(int, input().split(' ')))
	day_taste = {}
	for i in range(N):
		(P, Q) = list(map(int, input().split(' ')))
		if P not in day_taste:
			day_taste[P] = Q
		elif day_taste[P] < Q:
			day_taste[P] = Q
	taste = [i for i in day_taste.values()]
	max_tastiness = max(taste)
	taste.remove(max_tastiness)
	max_tastiness = max_tastiness + max(taste)
	print(max_tastiness)


t = int(input())
for tc in range(t):
	(n, m) = map(int, input().split())
	arr = []
	for j in range(n):
		(d, v) = map(int, input().split())
		arr.append([v, d])
	arr.sort(reverse=True)
	res = 0
	d = set()
	k = 0
	for i in range(n):
		if arr[i][1] not in d:
			res += arr[i][0]
			d.add(arr[i][1])
			k += 1
		if k == 2:
			break
	print(res)


import sys

def get_ints():
	return list(map(int, sys.stdin.readline().strip().split()))
t = int(input())
while t:
	(n, m) = get_ints()
	ar = [None] * m
	for i in range(m):
		ar[i] = 0
	for i in range(n):
		(a, b) = get_ints()
		a = a - 1
		ar[a] = max(ar[a], b)
	ar.sort()
	print(ar[-1] + ar[-2])
	t = t - 1


t = int(input())
while t:
	(n, m) = [int(x) for x in input().split()]
	ar = [None] * m
	for i in range(m):
		ar[i] = 0
	for i in range(n):
		(a, b) = [int(x) for x in input().split()]
		a = a - 1
		ar[a] = max(ar[a], b)
	ar.sort()
	print(ar[-1] + ar[-2])
	t = t - 1


t = int(input())
for _ in range(t):
	d = dict()
	(n, m) = map(int, input().split())
	for i in range(n):
		(day, v) = map(int, input().split())
		try:
			if v > d[day]:
				d[day] = v
		except KeyError:
			d[day] = v
	temp = []
	for j in d:
		temp.append(d[j])
	temp.sort()
	print(temp[len(temp) - 1] + temp[len(temp) - 2])


for i in range(int(input())):
	(n, m) = map(int, input().split())
	ans = 0
	d = []
	for j in range(n):
		v = list(map(int, input().split()))
		v.reverse()
		d.append(v)
	d.sort()
	maxi = d[n - 1][0]
	for j in range(n - 2, -1, -1):
		if d[j][1] != d[-1][1]:
			ans += d[j][0]
			break
	ans += maxi
	print(ans)


t = int(input())
for _ in range(t):
	(dishes, num_days) = map(int, input().split())
	taste_l = [0] * num_days
	for _ in range(dishes):
		(day, taste) = map(int, input().split())
		if taste_l[day - 1] < taste:
			taste_l[day - 1] = taste
	a = max(taste_l)
	taste_l.remove(a)
	b = max(taste_l)
	print(a + b)


t = int(input())
for _ in range(t):
	(dishes, num_days) = map(int, input().split())
	taste_l = [0] * num_days
	for _ in range(dishes):
		(day, taste) = map(int, input().split())
		taste_l[day - 1] = max(taste_l[day - 1], taste)
	taste_l.sort()
	print(taste_l[-1] + taste_l[-2])


T = int(input())
for i in range(T):
	(n, m) = list(map(int, input().split()))
	val = [0] * m
	for i in range(n):
		(d, v) = list(map(int, input().split()))
		if val[d - 1] <= v:
			val[d - 1] = v
	val.sort()
	print(val[-1] + val[-2])


t = int(input())
while t > 0:
	t -= 1
	tmpText1 = input()
	n = int(tmpText1.split(' ')[0])
	m = int(tmpText1.split(' ')[1])
	arr = [0 for i in range(m)]
	for i in range(n):
		tmpText2 = input()
		d = int(tmpText2.split(' ')[0])
		v = int(tmpText2.split(' ')[1])
		if arr[d - 1] < v:
			arr[d - 1] = v
	arr.sort()
	tot = arr[m - 2] + arr[m - 1]
	print(tot)


tc = int(input())
for c in range(tc):
	(n, m) = map(int, input().split())
	arr = [-1] * (m + 1)
	for _ in range(n):
		(d, v) = map(int, input().split())
		arr[d] = max(arr[d], v)
	m = -1
	sm = -1
	for i in arr:
		if i >= m:
			sm = m
			m = i
		elif i > sm:
			sm = i
	print(m + sm)


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	hash_map = {}
	for j in range(n):
		(days, tastiness) = map(int, input().split())
		if days in hash_map:
			if hash_map[days] < tastiness:
				hash_map[days] = tastiness
		else:
			hash_map[days] = tastiness
	taste = list(hash_map.values())
	taste = sorted(taste, reverse=True)
	print(taste[0] + taste[1])


from collections import defaultdict
t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	d = defaultdict(int)
	for i in range(n):
		(g, v) = map(int, input().split())
		if d[g] < v:
			d[g] = v
	l = sorted(d.values(), reverse=True)
	print(l[0] + l[1])


t = int(input())
for i in range(t):
	arr = []
	day = []
	(n, m) = map(int, input().split())
	sum = 0
	for m in range(n):
		(d, v) = map(int, input().split())
		arr.append([d, v])
	arr.sort(reverse=True, key=lambda x: x[1])
	for k in range(n):
		if arr[k][0] not in day:
			sum += arr[k][1]
			day.append(arr[k][0])
		if len(day) == 2:
			break
	print(sum)


t = int(input())
for _ in range(t):
	days_dist = {}
	(n, m) = map(int, input().split())
	for i in range(n):
		(d, v) = map(int, input().split())
		if d in days_dist:
			if days_dist[d] < v:
				days_dist[d] = v
		else:
			days_dist[d] = v
	tot = 0
	for a in range(2):
		(max_1, val) = (0, 0)
		for ele in days_dist:
			if days_dist[ele] > max_1:
				max_1 = days_dist[ele]
				val = ele
		tot += max_1
		del days_dist[val]
	print(tot)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	mylist = []
	for i in range(n):
		(day, value) = map(int, input().split())
		mylist.append((value, day))
	mylist.sort(reverse=True)
	value = mylist[0][0]
	day = mylist[0][1]
	index = 1
	while mylist[index][1] == day:
		index += 1
	value += mylist[index][0]
	print(value)


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	mylist = []
	for i in range(n):
		(day, value) = map(int, input().split())
		mylist.append((value, day))
	mylist.sort(key=lambda x: -1 * x[0])
	value = mylist[0][0]
	day = mylist[0][1]
	index = 1
	while mylist[index][1] == day:
		index += 1
	value += mylist[index][0]
	print(value)


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	d = {}
	for i in range(n):
		(a, v) = map(int, input().split())
		if a not in d:
			d[a] = v
		else:
			d[a] = max(d[a], v)
	l = sorted(d.values())
	print(l[-1] + l[-2])


for _ in range(int(input())):
	(N, M) = map(int, input().split())
	arr = dict()
	for i in range(N):
		(d, v) = map(int, input().split())
		if d not in arr:
			arr[d] = v
		else:
			val = max(arr[d], v)
			arr[d] = val
	brr = sorted(arr.values())
	print(brr[-1] + brr[-2])


t = int(input())
for _ in range(t):
	(n, m) = map(int, input().split())
	mp = {}
	for _ in range(n):
		(d, v) = map(int, input().split())
		if d <= m:
			if d not in mp:
				mp[d] = v
			elif v > mp[d]:
				mp[d] = v
	mp = sorted(mp.items(), key=lambda x: x[1], reverse=True)
	tastiness = 0
	count = 0
	for (x, y) in mp:
		if count != 2:
			tastiness += y
			count += 1
	print(tastiness)


t = int(input())
for i in range(t):
	(n, k) = map(int, input().split())
	dict1 = dict()
	for i in range(n):
		(d, v) = map(int, input().split())
		if d not in dict1:
			dict1[d] = v
		else:
			max1 = 0
			max1 = max(dict1[d], v)
			dict1[d] = max1
	list1 = sorted(dict1.values())
	print(list1[-1] + list1[-2])


t = int(input())
for i in range(t):
	(n, m) = map(int, input().split())
	dict1 = dict()
	for i in range(n):
		(d, v) = map(int, input().split())
		if d not in dict1:
			dict1[d] = v
		else:
			max1 = max(dict1[d], v)
			dict1[d] = max1
	tastes = sorted(dict1.values())
	print(tastes[-1] + tastes[-2])


try:
	t = int(input())
	for i in range(t):
		(n, k) = map(int, input().split())
		dict1 = dict()
		for i in range(n):
			(d, v) = map(int, input().split())
			if d not in dict1:
				dict1[d] = v
			else:
				max1 = max(dict1[d], v)
				dict1[d] = max1
		tastes = sorted(dict1.values())
		print(tastes[-1] + tastes[-2])
except:
	pass


try:
	t = int(input())
	for i in range(t):
		(N, K) = map(int, input().rstrip().split())
		dayDict = dict()
		for i in range(N):
			(day, tastiness) = map(int, input().rstrip().split())
			if day not in dayDict:
				dayDict[day] = tastiness
			else:
				maxTaste = max(dayDict[day], tastiness)
				dayDict[day] = maxTaste
		tastes = sorted(dayDict.values())
		print(tastes[-1] + tastes[-2])
except:
	pass


from collections import defaultdict
T = int(input())
for _ in range(T):
	(N, M) = list(map(int, input().split()))
	L = defaultdict(lambda : [])
	for i in range(N):
		(Day, Value) = list(map(int, input().split()))
		L[Day].append(Value)
	max = -1
	for i in L:
		for j in L[i]:
			if max < j:
				max = j
				index = i
	del L[index]
	A = max
	max = -1
	for i in L:
		for j in L[i]:
			if max < j:
				max = j
	B = max
	print(A + B)


from sys import stdin
try:
	t = eval(stdin.readline())
	for _ in range(t):
		(n, m) = [int(x) for x in stdin.readline().split()]
		Dict = {x: 0 for x in range(1, m + 1)}
		for _ in range(n):
			(x, v) = [int(x) for x in stdin.readline().split()]
			if v > Dict[x]:
				Dict[x] = v
		freq = list(Dict.values())
		answer = max(freq)
		freq.remove(answer)
		answer += max(freq)
		print(answer)
except:
	pass


for _ in range(int(input())):
	(n, m) = map(int, input().split())
	res = []
	for i in range(n):
		a = list(map(int, input().split()))
		res.append(a)
	res.sort(key=lambda x: x[1])
	ans = res[-1][1]
	t = res[-1][0]
	for i in range(n - 2, -1, -1):
		if res[i][0] != t:
			ans += res[i][1]
			break
	print(ans)