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