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: interview

Starter code:

Solutions:
# cook your dish here
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]
 # print(d)
 if len(d)<3:
  print(0)
 else:
  kd=list(d.values())
  kd.sort()
  # print(kd)
  print(kd[-1]+kd[-2]+kd[-3])


# cook your dish here
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]
 # print(d)
 if len(d)<3:
  print(0)
 else:
  kd=list(d.values())
  kd.sort()
  # print(kd)
  print(kd[-1]+kd[-2]+kd[-3])


# cook your dish here
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]
 # print(d)
 if len(d)<3:
  print(0)
 else:
  kd=list(d.values())
  kd.sort()
  # print(kd)
  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)
 #print(d)
 
 l=sorted(d.items(),key=itemgetter(1))[::-1]
 #print(l)
 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])
 #print(y)
 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])
 #print(y)
 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)


# cook your dish here
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])

 #print(d)
 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)

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])

 #print(d)
 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])

t=int(input())
for r in range(0,t):
 n=int(input())
 x,y=[],[]
 d={}
 for p in range(n):
  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()
 #print(p)

 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])

# Author: Dancing Monkey | Created: 09.DEC.2018

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()
  #print(a)
  q=a[0][0]
  z=[]
  for i in range(1,n):
    #print(a[i][0],q)
    if a[i][0]!=q:
      z.append(a[i-1][1])
      #print(a[i])
      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])