Chef hates unoptimized codes and people who write such codes. One fine day he decided to look through the kitchen's codebase and found a function whose pseudo-code is given here:

input: integer N, list X[1, 2, ..., N], list Y[1, 2, ..., N]

output: integer res

function:

set res = 0;
for i := 1 to N do
for j := 1 to N do
for k := 1 to N do
if (X[i] = X[j]) OR (X[j] = X[k]) OR (X[k] = X[i])
continue
else
set res = max(res, Y[i] + Y[j] + Y[k])
return res

Luckily enough this code gets triggered only if the Head Chef makes a submission. But still there is a possibility that this can crash the judge. So help Chef by writing a new function which does the same thing but is faster.

-----Input-----
- The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
- The first line of each test case contains an integer N denoting the number of elements in the two lists.
- The i-th of the next N lines contains a pair of space-separated integers denoting the values of X[i] and Y[i] respectively.

-----Output-----
For each test case, output an integer corresponding to the return value of the function.

-----Constraints-----
- 1 ≤ T ≤ 10
- 1 ≤ N ≤ 105
- 1 ≤ X[i], Y[i] ≤ 108

-----Example-----
Input
2
3
1 3
3 1
1 2
5
1 3
2 4
1 2
3 2
3 4

Output
0
11

-----Explanation-----
Testcase 2: The maximum is attained when i = 1, j = 2 and k = 5. This leads to res being 3 + 4 + 4 = 11. This value is attained in other iterations as well, but it never exceeds this, and hence this is the answer.

Difficulty: UNKNOWN_DIFFICULTY

Starter code:

Solutions:
for _ in range(int(input())):
	d = dict()
	ls = []
	for i in range(int(input())):
		ls = list(map(int, input().split()))
		if ls[0] in d:
			d[ls[0]] = max(ls[1], d[ls[0]])
		else:
			d[ls[0]] = ls[1]
	if len(d) < 3:
		print(0)
	else:
		kd = list(d.values())
		kd.sort()
		print(kd[-1] + kd[-2] + kd[-3])


try:
	from sys import stdin as si, stdout as so
	for _ in range(int(si.readline())):
		m = {}
		n = int(si.readline())
		for i in range(n):
			(a, b) = map(int, si.readline().split())
			if a not in m:
				m[a] = b
			else:
				m[a] = max(m[a], b)
		if len(m) < 3:
			so.write(str(0) + '\n')
		else:
			l = list(m.values())
			l.sort()
			so.write(str(l[-1] + l[-2] + l[-3]) + '\n')
except:
	pass


def optimize(d):
	l = list(d.keys())
	if len(l) < 3:
		return 0
	else:
		j = []
		for i in l:
			j.append(d[i])
		j.sort()
		return j[len(j) - 1] + j[len(j) - 2] + j[len(j) - 3]
try:
	for _ in range(int(input())):
		(x, y, d) = ([], [], {})
		for i in range(int(input())):
			j = list(map(int, input().strip().split()))
			x.append(j[0])
			y.append(j[1])
			if x[i] not in d:
				d[x[i]] = y[i]
			else:
				d[x[i]] = max(y[i], d[x[i]])
		print(optimize(d))
except EOFError as e:
	pass


from collections import defaultdict
from operator import itemgetter
for _ in range(int(input())):
	n = int(input())
	d = defaultdict(list)
	for i in range(n):
		(x, y) = map(int, input().split())
		if not d[x]:
			d[x].append(y)
		else:
			d[x][0] = max(d[x][0], y)
	l = sorted(d.items(), key=itemgetter(1))[::-1]
	try:
		print(sum(l[0][1] + l[1][1] + l[2][1]))
	except:
		print(0)


for _ in range(int(input())):
	n = int(input())
	d = {}
	for i in range(n):
		(x, y) = list(map(int, input().split()))
		if x not in d:
			d[x] = []
			d[x].append(y)
		else:
			d[x][0] = max(d[x][0], y)
	y = []
	for v in d:
		y.extend(d[v])
	if len(y) >= 3:
		v1 = max(y)
		y.remove(v1)
		v2 = max(y)
		y.remove(v2)
		v3 = max(y)
		y.remove(v3)
		print(v1 + v2 + v3)
	else:
		print(0)


from collections import defaultdict
from operator import itemgetter
for _ in range(int(input())):
	n = int(input())
	d = defaultdict(list)
	for i in range(n):
		(x, y) = list(map(int, input().split()))
		if not d[x]:
			d[x].append(y)
		else:
			d[x][0] = max(d[x][0], y)
	y = []
	for v in d:
		y.extend(d[v])
	if len(y) >= 3:
		v1 = max(y)
		y.remove(v1)
		v2 = max(y)
		y.remove(v2)
		v3 = max(y)
		y.remove(v3)
		print(v1 + v2 + v3)
	else:
		print(0)


T = int(input())
for _ in range(T):
	res = 0
	N = int(input())
	X = []
	Y = []
	for i in range(N):
		words = input().split()
		X.append(int(words[0]))
		Y.append(int(words[1]))
	d = {}
	for i in range(N):
		if X[i] not in d.keys():
			d[X[i]] = []
			d[X[i]].append(Y[i])
		else:
			d[X[i]].append(Y[i])
	sum_lst = []
	for key in d.keys():
		maxi = d[key][0]
		for num in d[key]:
			if maxi < num:
				maxi = num
		sum_lst.append(maxi)
	if len(sum_lst) >= 3:
		max1 = max(sum_lst)
		sum_lst.remove(max1)
		max2 = max(sum_lst)
		sum_lst.remove(max2)
		max3 = max(sum_lst)
		res = max1 + max2 + max3
	else:
		res = 0
	print(res)


for r in range(int(input())):
	(x, y, d) = ([], [], {})
	for p in range(int(input())):
		j = list(map(int, input().split()))
		(x.append(j[0]), y.append(j[1]))
		if x[p] not in d:
			d[x[p]] = y[p]
		else:
			d[x[p]] = max(y[p], d[x[p]])
	l = list(d.keys())
	if len(l) < 3:
		print(0)
	else:
		j = []
		for x in l:
			j.append(d[x])
		j.sort()
		print(j[len(j) - 1] + j[len(j) - 2] + j[len(j) - 3])


import sys
import queue
t = int(input())
while t:
	n = int(input())
	d = {}
	for i in range(n):
		line = input().split()
		x = int(line[0])
		y = int(line[1])
		if x not in d:
			d[x] = y
		else:
			d[x] = max(d[x], y)
	p = list(d.items())
	n = len(p)
	for i in range(n):
		p[i] = (p[i][1], p[i][0])
	p.sort()
	if len(p) > 2:
		n = len(p)
		sys.stdout.write(str(p[n - 1][0] + p[n - 2][0] + p[n - 3][0]) + '\n')
	else:
		sys.stdout.write('0\n')
	t -= 1


t = int(input())
while t:
	t -= 1
	n = int(input())
	d = dict()
	for i in range(n):
		(x, y) = map(int, input().split())
		f = d.get(x)
		if f == None:
			d[x] = y
		else:
			d[x] = max(d[x], y)
	z = sorted(d.values())[::-1]
	l = len(z)
	if l < 3:
		print(0)
	else:
		print(z[0] + z[1] + z[2])


for _ in range(int(input())):
	n = int(input())
	l = []
	for i in range(n):
		(x, y) = map(int, input().split())
		l.append((y, x))
	l.sort(reverse=True)
	(y1, x1) = l[0]
	y2 = x2 = y3 = x3 = -1
	i = 1
	while i < n:
		(y, x) = l[i]
		if x == x1:
			p = 0
		else:
			(y2, x2) = (y, x)
			break
		i += 1
	if i == n:
		print(0)
		continue
	while i < n:
		(y, x) = l[i]
		if x == x1 or x == x2:
			p = 1
		else:
			(y3, x3) = (y, x)
			break
		i += 1
	if i == n:
		print(0)
		continue
	print(y3 + y2 + y1)


for _ in range(int(input())):
	n = int(input())
	l = []
	x = set()
	res = 0
	for z in range(n):
		(xi, yi) = list(map(int, input().split()))
		x.add(xi)
		l.append([xi, yi])
	l.sort(reverse=True, key=lambda q: q[1])
	if len(x) < 3:
		res = 0
	else:
		temp = []
		for i in range(n):
			if len(temp) == 3:
				break
			elif l[i][0] in temp:
				continue
			else:
				res += l[i][1]
				temp.append(l[i][0])
	print(res)


t = int(input())
for i in range(t):
	a = []
	n = int(input())
	for i in range(n):
		(x, y) = [int(i) for i in input().split()]
		a.append((x, y))
	a.sort()
	q = a[0][0]
	z = []
	for i in range(1, n):
		if a[i][0] != q:
			z.append(a[i - 1][1])
			q = a[i][0]
	z.append(a[n - 1][1])
	l = len(z)
	if l < 3:
		print(0)
	else:
		z.sort()
		print(z[l - 1] + z[l - 2] + z[l - 3])


for T in range(int(input())):
	N = int(input())
	d = dict()
	for i in range(N):
		(x, y) = list(map(int, input().split()))
		f = d.get(x)
		if f == None:
			d[x] = y
		else:
			d[x] = max(f, y)
	l = len(d)
	if l < 3:
		print(0)
	else:
		Y = sorted(list(d.items()), key=lambda x: x[1])
		print(Y[l - 1][1] + Y[l - 2][1] + Y[l - 3][1])