Problem:
 Score : 500 points    Problem Statement We have N camels numbered 1,2,\ldots,N .
Snuke has decided to make them line up in a row.  The happiness of Camel i will be L_i if it is among the K_i frontmost camels, and R_i otherwise.  Snuke wants to maximize the total happiness of the camels. Find the maximum possible total happiness of the camel.  Solve this problem for each of the T test cases given.      Constraints  All values in input are integers.  1 \leq T \leq 10^5  1 \leq N \leq 2 \times 10^{5}  1 \leq K_i \leq N  1 \leq L_i, R_i \leq 10^9  The sum of values of N in each input file is at most 2 \times 10^5 .         Input Input is given from Standard Input in the following format:  T  \mathrm{case}_1  \vdots  \mathrm{case}_T   Each case is given in the following format:  N  K_1  L_1  R_1  \vdots  K_N  L_N  R_N       Output Print T lines. The i -th line should contain the answer to the i -th test case.        Sample Input 1 3
2
1 5 10
2 15 5
3
2 93 78
1 71 59
3 57 96
19
19 23 16
5 90 13
12 85 70
19 67 78
12 16 60
18 48 28
5 4 24
12 97 97
4 57 87
19 91 74
18 100 76
7 86 46
9 100 57
3 76 73
6 84 93
1 6 84
11 75 94
19 15 3
12 11 34      Sample Output 1 25
221
1354   In the first test case, it is optimal to line up the camels in the order 2, 1 .  Camel 1 is not the frontmost camel, so its happiness will be 10 .  Camel 2 is among the two frontmost camels, so its happiness will be 15 .    In the second test case, it is optimal to line up the camels in the order 2, 1, 3 .  Camel 1 is among the two frontmost camels, so its happiness will be 93 .  Camel 2 is the frontmost camel, so its happiness will be 71 .  Camel 3 is among the three frontmost camels, so its happiness will be 57 .

Solution (Python):






import sys
input = sys.stdin.readline

import math

import bisect
import heapq
from collections import defaultdict
from collections import deque
from collections import Counter
from functools import lru_cache





MOD = 10**9+7
INF = float('inf')
AZ = "abcdefghijklmnopqrstuvwxyz"






def I(): return int(input().strip())
def S(): return input().strip()
def IL(): return list(map(int,input().split()))
def SL(): return list(map(str,input().split()))
def ILs(n): return list(int(input()) for _ in range(n))
def SLs(n): return list(input().strip() for _ in range(n))
def ILL(n): return [list(map(int, input().split())) for _ in range(n)]
def SLL(n): return [list(map(str, input().split())) for _ in range(n)]


def P(arg): print(arg); return
def Y(): print("Yes"); return
def N(): print("No"); return
def E(): exit()
def PE(arg): print(arg); exit()
def YE(): print("Yes"); exit()
def NE(): print("No"); exit()


def DD(arg): return defaultdict(arg)


def inv(n): return pow(n, MOD-2, MOD)


kaijo_memo = []
def kaijo(n):
  if(len(kaijo_memo) > n): return kaijo_memo[n]
  if(len(kaijo_memo) == 0): kaijo_memo.append(1)
  while(len(kaijo_memo) <= n): kaijo_memo.append(kaijo_memo[-1] * len(kaijo_memo) % MOD)
  return kaijo_memo[n]

gyaku_kaijo_memo = []
def gyaku_kaijo(n):
  if(len(gyaku_kaijo_memo) > n): return gyaku_kaijo_memo[n]
  if(len(gyaku_kaijo_memo) == 0): gyaku_kaijo_memo.append(1)
  while(len(gyaku_kaijo_memo) <= n): gyaku_kaijo_memo.append(gyaku_kaijo_memo[-1] * pow(len(gyaku_kaijo_memo),MOD-2,MOD) % MOD)
  return gyaku_kaijo_memo[n]

def nCr(n,r):
  if n == r: return 1
  if n < r or r < 0: return 0
  ret = 1
  ret = ret * kaijo(n) % MOD
  ret = ret * gyaku_kaijo(r) % MOD
  ret = ret * gyaku_kaijo(n-r) % MOD
  return ret


def factorization(n):
  arr = []
  temp = n
  for i in range(2, int(-(-n**0.5//1))+1):
    if temp%i==0:
      cnt=0
      while temp%i==0: 
        cnt+=1 
        temp //= i
      arr.append([i, cnt])
  if temp!=1: arr.append([temp, 1])
  if arr==[]: arr.append([n, 1])
  return arr


def make_divisors(n):
  divisors = []
  for i in range(1, int(n**0.5)+1):
    if n % i == 0:
      divisors.append(i)
      if i != n // i: 
        divisors.append(n//i)
  return divisors


def make_primes(N):
  max = int(math.sqrt(N))
  seachList = [i for i in range(2,N+1)]
  primeNum = []
  while seachList[0] <= max:
    primeNum.append(seachList[0])
    tmp = seachList[0]
    seachList = [i for i in seachList if i % tmp != 0]
  primeNum.extend(seachList)
  return primeNum


def gcd(a, b):
    while b: a, b = b, a % b
    return a


def lcm(a, b):
    return a * b // gcd (a, b)


def count_bit(n):
  count = 0
  while n:
    n &= n-1
    count += 1
  return count


def base_10_to_n(X, n):
  if X//n: return base_10_to_n(X//n, n)+[X%n]
  return [X%n]

def base_n_to_10(X, n):
  return sum(int(str(X)[-i-1])*n**i for i in range(len(str(X))))

def base_10_to_n_without_0(X, n):
  X -= 1
  if X//n: return base_10_to_n_without_0(X//n, n)+[X%n]
  return [X%n]


def int_log(n, a):
  count = 0
  while n>=a:
    n //= a
    count += 1
  return count




Q = I()


for _ in range(Q):
  N = I()
  data = ILL(N)
  Mdic = DD(list)
  Udic = DD(list)
  Mcount = 0
  Ucount = 0
  ans = 0
  for K,L,R in data:
    if L>=R:
      Mdic[K-1].append(L-R)
      ans += R
      Mcount += 1
    else:
      Udic[N-1-K].append(R-L)
      ans += L
      Ucount += 1
  q = []
  for i in range(N):
    for v in Mdic[i]:
      ans += v
      heapq.heappush(q,v)
    while len(q)>i+1:
      ans -= heapq.heappop(q)
  q = []
  for i in range(N):
    for v in Udic[i]:
      ans += v
      heapq.heappush(q,v)
    while len(q)>i+1:
      ans -= heapq.heappop(q)
  print(ans)

Solution (Python):
from heapq import*
i=input
for _ in'_'*int(i()):
 n,s,x,*y=int(i()),0,[]
 for _ in'_'*n:k,l,r=t=[*map(int,i().split())];x+=[t]*(l>r);y+=[(n-k,r,l)]*(l<=r)
 for x in x,y:
  x.sort();n,*h=len(x),
  while n:
   n-=1
   while x and x[-1][0]>n:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
  for*_,r in x+h:s+=r
 print(s)

Solution (Python):
from heapq import*
i=input
for _ in'_'*int(i()):
 n,s,x,*y=int(i()),0,[]
 for _ in'_'*n:k,l,r=map(int,i().split());x+=[(k,l,r)]*(l>r);y+=[(n-k,r,l)]*(l<=r)
 for x in x,y:
  x.sort();n,*h=len(x),
  while n:
   n-=1
   while x and x[-1][0]>n:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
  for*_,r in x+h:s+=r
 print(s)

Solution (Python):
from heapq import*
i=input
for _ in'_'*int(i()):
 n,s,x,*y=int(i()),0,[]
 for _ in'_'*n:
  k,l,r=map(int,i().split())
  if l>r:x+=(k,l,r),
  else:y+=(n-k,r,l),
 for x in x,y:
  x.sort();n,*h=len(x),
  while n:
   n-=1
   while x and x[-1][0]>n:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
  for*_,r in x+h:s+=r
 print(s)

Solution (Python):
import sys,collections as cl,bisect as bs,heapq as hq
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
	return list(map(int,input().split()))
def m(): 
	return map(int,input().split())
def onem(): 
	return int(input())
def s(x): 
	a = []
	if len(x) == 0:
		return []
	aa = x[0]
	su = 1
	for i in range(len(x)-1):
		if aa != x[i+1]:
			a.append([aa,su])
			aa = x[i+1]
			su = 1
		else:
			su += 1
	a.append([aa,su])
	return a
def jo(x): 
	return " ".join(map(str,x))
def max2(x): 
	return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
	ll = 0
	rr = r
	while True:
		mid = (ll+rr)//2

	if rr == mid:
		return ll
	if (ここに評価入れる):
		rr = mid
	else:
		ll = mid+1
"""

t = onem()

for _ in range(t):
	n = onem()
	L = []
	R = []
	ans = 0
	for i in range(n):
		k,l,r = m()
		if l >= r:
			L.append([k,l-r])
			ans += r
		else:
			R.append([n-k + 1,r-l])
			ans += l
	L.sort()
	R.sort()

	po = []
	ii = 0
	for i in range(n):
		while ii < len(L):
			if L[ii][0] == i+1:
				hq.heappush(po,L[ii][1])
				ii += 1
			else:
				break
		while len(po) > i+1:
			hq.heappop(po)
	ans += sum(po)
	po = []
	ii = 0
	for i in range(n):
		while ii < len(R):
			if R[ii][0] == i+1:
				hq.heappush(po,R[ii][1])
				ii += 1
			else:
				break
		while len(po) > i:
			hq.heappop(po)
	ans += sum(po)
	print(ans)

Solution (Python):
import heapq
t = int(input())
for _ in range(t):
    n = int(input())
    L, R = [], []
    N = [[] for j in range(n)]
    P = [[] for j in range(n + 1)]
    for i in range(n):
        k, l, r = map(int, input().split())
        if l - r > 0:
            N[k - 1].append(i)
        else:
            P[k].append(i)
        L.append(l)
        R.append(r)
    ans = sum([min(L[i], R[i]) for i in range(n)])
    S, T = [], []
    for j in range(n):
        for i in N[j]:
            heapq.heappush(S, L[i] - R[i])
        for i in P[n - 1 - j]:
            heapq.heappush(T, R[i] - L[i])
        while len(S) > j + 1:
            heapq.heappop(S)
        while len(T) > j + 1:
            heapq.heappop(T)
    print(ans + sum(S) + sum(T))

Solution (Python):
import math

import itertools
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit


ipt = stdin.readline
setrecursionlimit(10**7)

def main():
    t = int(ipt())
    for _ in range(t):
        n = int(ipt())
        camp = [[] for i in range(n+1)]
        camm = [[] for i in range(n+1)]
        ans = 0
        pn = 0
        for i in range(n):
            k,l,r = map(int,ipt().split())
            ans += min(r,l)
            if l >= r:
                camp[k].append(l-r)
                pn += 1
            else:
                camm[k].append(r-l)

        hq = []
        for i in range(1,n+1):
            for j in camp[i]:
                hpq.heappush(hq,j)
            t = len(hq)-i
            for j in range(t):
                hpq.heappop(hq)
        for i in hq:
            ans += i
            
        hq = []
        for i in range(n):
            for j in camm[n-i]:
                hpq.heappush(hq,j)
            t = len(hq)-i
            for j in range(t):
                hpq.heappop(hq)
        for i in hq:
            ans += i

        print(ans)



    return None

if __name__ == '__main__':
    main()

Solution (Python):
import heapq
t = int(input())
for i in range(t):
    n = int(input())
    ans = 0
    cl,cr = 0,0
    lisl = []
    lisr = []
    rs = 0
    ls = 0
    for i in range(n):
        k,l,r = map(int,input().split())
        a = r-l
        s = (l>r)
        if a<0:
            lisl.append([k,l,r,-a,s])
            rs += r
        else:
            lisr.append([k,l,r,a,s])
            ls += l
    lisl.sort(key=lambda x: x[0])
    lisr.sort(key=lambda x: x[0],reverse=1)
    h = []
    cntl = 0
    cntr = 0
    for i in lisl:
        heapq.heappush(h,i[3])
        cntl += 1
        if cntl > i[0]:
            heapq.heappop(h)
            cntl -= 1
    hr = []
    for i in lisr:
        heapq.heappush(hr,i[3])
        cntr += 1
        if cntr > n-i[0]:
            heapq.heappop(hr)
            cntr -= 1
    print(rs+sum(h)+ls+sum(hr))

Solution (Python):
from heapq import*
i=input
for _ in'_'*int(i()):
 n,s,x,*y=int(i()),0,[]
 for _ in'_'*n:
  k,l,r=map(int,i().split())
  if l>r:x+=(k,l,r),
  else:y+=(n-k,r,l),
 for x in(x,y):
  x.sort();n,*h=len(x),
  while n:
   n-=1
   while x and x[-1][0]>n:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
  for*_,r in x+h:s+=r
 print(s)

Solution (Python):
import heapq
t = int(input())
for i in range(t):
    n = int(input())
    ans = 0
    cl,cr = 0,0
    lisl = []
    lisr = []
    rs = 0
    ls = 0
    for i in range(n):
        k,l,r = map(int,input().split())
        a = r-l
        s = (l>r)
        if a<0:
            lisl.append([k,l,r,-a,s])
            rs += r
        else:
            lisr.append([k,l,r,a,s])
            ls += l
    
    lisl.sort(key=lambda x: x[0])
    
    lisr.sort(key=lambda x: x[0],reverse=1)
    
    h = []
    cntl = 0
    cntr = 0
    
    
    for i in lisl:
        heapq.heappush(h,i[3])
        cntl += 1
        if cntl > i[0]:
            heapq.heappop(h)
            cntl -= 1
    
    hr = []
    for i in lisr:
        heapq.heappush(hr,i[3])
        cntr += 1
        if cntr > n-i[0]:
            heapq.heappop(hr)
            cntr -= 1
    
    
    
    print(rs+sum(h)+ls+sum(hr))

Solution (Python):
from heapq import*
i=input
def f(x):
 x.sort();s,n,*h=0,len(x)
 while n:
  n-=1
  while x and x[-1][0]>n:k,l,r=x.pop();heappush(h,(r-l,l,r))
  if h:s+=heappop(h)[1]
 return s+sum(r for*_,r in x+h)
for _ in'_'*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=map(int,i().split())
  if l>r:x+=(k,l,r),
  else:y+=(n-k,r,l),
 print(f(x)+f(y))

Solution (Python):
import sys
from operator import itemgetter
from heapq import heappush, heappop
input = sys.stdin.readline


def simulate(camels):
    camels.sort(key=itemgetter(0))
    queue = []
    ans = 0
    for k, l, r in camels:
        ans += l
        if len(queue) < k:
            
            heappush(queue, l - r)
        else:
            heappush(queue, l - r)
            d = heappop(queue)
            ans -= d
    return ans


def solve():
    n = int(input())
    camels = [tuple(map(int, input().split())) for _ in range(n)]

    ans = 0
    camels_l = []
    camels_r = []
    for k, l, r in camels:
        if k == n or l == r:
            ans += l
        elif l > r:
            camels_l.append((k, l, r))
        else:
            
            camels_r.append((n - k, r, l))

    ans += simulate(camels_l)
    ans += simulate(camels_r)

    print(ans)


t = int(input())
for _ in range(t):
    solve()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


def init(bit, values):
    for i,v in enumerate(values):
        add(bit,i+1,v)

def query(bit,i):
    res = 0
    while i > 0:
        res += bit[i]
        i -= i&(-i)
    return res


def add(bit,i,x):
    if i==0:
        raise RuntimeError
    while i <= len(bit)-1:
        bit[i] += x
        i += i&(-i)
    return


t = int(input())
ANS = [None]*t
from collections import defaultdict
from heapq import heappop as hpp, heappush as hp
for iii in range(t):
    n = int(input())
    d1 = defaultdict(list)
    d0 = defaultdict(list)
    lr = [None]*n
    for i in range(n):
        k,l,r = list(map(int, input().split()))
        lr[i] = (l,r)
        if l-r>=0:
            d1[k].append((l-r, i))
        else:
            d0[k].append((r-l, i))
            
    sl = set()
    sr = set()
    h = []
    for i in range(1,n+1):
        if i not in d1:
            continue
        for item in d1[i]:
            hp(h, item)
        while i<len(h):
            *_,ii = hpp(h)
            sr.add(ii)
    for *_,i in h:
        sl.add(i)
    h = []
    for i in range(n, 0, -1):
        if i not in d0:
            continue
        for item in d0[i]:
            hp(h,item)
        while (n-i)<len(h):
            *_,ii = hpp(h)
            sl.add(ii)
    for *_,i in h:
        sr.add(i)
    ans = 0

    for i in sl:
        ans += lr[i][0]
    for i in sr:
        ans += lr[i][1]
    ANS[iii] = ans
write("\n".join(map(str, ANS)))

Solution (Python):
import sys
import heapq


input = sys.stdin.readline

T = int(input())

def solve():
    N = int(input())
    ls = []
    rs = []
    heapq.heapify(ls)
    heapq.heapify(rs)
    for _ in range(N):
        k, l, r = map(int, input().split())
        if l - r >= 0:
            heapq.heappush(ls, (k, l, r))
        else:
            heapq.heappush(rs, (N-k, l, r))
    ans = 0
    ls_l = []
    heapq.heapify(ls_l)
    while len(ls) != 0:
        k, l, r = heapq.heappop(ls)
        heapq.heappush(ls_l, (l-r))
        ans += r
        while len(ls_l) > k:
            heapq.heappop(ls_l)
    rs_r = []
    heapq.heapify(rs_r)
    while len(rs) != 0:
        k, l, r = heapq.heappop(rs)
        heapq.heappush(rs_r, (r-l))
        ans += l
        while len(rs_r) > k:
            heapq.heappop(rs_r)
    while len(ls_l) != 0:
        ans += heapq.heappop(ls_l)
    while len(rs_r) != 0:
        ans += heapq.heappop(rs_r)
    print(ans)


for _ in range(T):
    solve()

Solution (Python):
import sys
import heapq


def _i(): return int(sys.stdin.readline().strip())


def _ia(): return map(int, sys.stdin.readline().strip().split())


def reward(n, d):
    s = []
    for i in range(n):
        for item in d.get(i, []):
            heapq.heappush(s, item)
        for _ in range(len(s), i+1, -1):
            _ = heapq.heappop(s)
    return sum(s)


def test():
    n = _i()
    ll, rr = {}, {}
    mn = ln = rn = 0
    for i in range(n):
        k, l, r = _ia()
        mn += min(l, r)
        if l >= r:
            ll[k-1] = ll.get(k-1, []) + [l-r]
            ln += 1
        else:
            rr[n-k-1] = rr.get(n-k-1, []) + [r-l]
            rn += 1

    return mn + reward(n, ll) + reward(n, rr)


def main():
    t = _i()
    ret = [test() for _ in range(t)]
    return "\n".join(map(str, ret))


if __name__ == "__main__":
    print(main())

Solution (Python):


import heapq
import sys
input=sys.stdin.readline

t=int(input())
for _ in range(t):
    n=int(input())
    arr=[list(map(int,input().split())) for _ in range(n)]
    q=[]
    ans=0
    camels1=[[] for _ in range(n+1)]
    camels2=[[] for _ in range(n+1)]
    for k,l,r in arr:
        if l>=r:
            camels1[k].append((l,r))
        else:
            camels2[k].append((l,r))
    for i in range(1,n+1):
        for l,r in camels1[i]:
            heapq.heappush(q,(l-r,l,r))
        while len(q)>i:
            _,_,r=heapq.heappop(q)
            ans+=r
    while len(q)!=0:
        _,l,_=heapq.heappop(q)
        ans+=l
    for i in range(n,0,-1):
        for l,r in camels2[i]:
            heapq.heappush(q,(r-l,l,r))
        while len(q)>(n-i):
            _,l,_=heapq.heappop(q)
            ans+=l
    while len(q)!=0:
        _,_,r=heapq.heappop(q)
        ans+=r
    print(ans)

Solution (Python):
from heapq import *
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

for _ in range(II()):
    n=II()
    ff=[]
    bb=[]
    ans=0
    for _ in range(n):
        k,l,r=MI()
        if l>r:ff.append((k,l,r))
        elif l<r:bb.append((n-k,l,r))
        else:ans+=r

    ff.sort()
    hp=[]
    for i,(k,l,r) in enumerate(ff):
        heappush(hp,l-r)
        ans+=l
        if i+1<len(ff) and ff[i+1][0]==k:continue
        while len(hp)>k:
            d=heappop(hp)
            ans-=d

    bb.sort()
    hp = []
    for i, (k, l, r) in enumerate(bb):
        heappush(hp, r-l)
        ans += r
        if i + 1 < len(bb) and bb[i + 1][0] == k: continue
        while len(hp) > k:
            d = heappop(hp)
            ans -= d

    print(ans)

Solution (Python):


import heapq
import sys
input=sys.stdin.readline

t=int(input())
for _ in range(t):
    n=int(input())
    arr=[list(map(int,input().split())) for _ in range(n)]
    q=[]
    ans=0
    camels1=[[] for _ in range(n+1)]
    camels2=[[] for _ in range(n+1)]
    for k,l,r in arr:
        ans+=min(l,r)
        if l>=r:
            camels1[k].append((l,r))
        else:
            camels2[k].append((l,r))
    for i in range(1,n+1):
        for l,r in camels1[i]:
            heapq.heappush(q,l-r)
        while len(q)>i:
            heapq.heappop(q)
    while len(q)!=0:
        ans+=heapq.heappop(q)
    for i in range(n,0,-1):
        for l,r in camels2[i]:
            heapq.heappush(q,r-l)
        while len(q)>(n-i):
            heapq.heappop(q)
    while len(q)!=0:
        ans+=heapq.heappop(q)
    print(ans)

Solution (Python):
from heapq import*
i=input
def f(x):
 x.sort();s,n,*h=0,len(x)
 while n:
  while x and x[-1][0]>=n:k,l,r=x.pop();heappush(h,(r-l,l,r))
  if h:s+=heappop(h)[1]
  n-=1
 return s+sum(r for*_,r in x+h)
for _ in'_'*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=map(int,i().split())
  if l>r:x+=(k,l,r),
  else:y+=(n-k,r,l),
 print(f(x)+f(y))

Solution (Python):
from heapq import*
i=input
s=sorted
def f(x):
 s,n,*h=0,len(x)
 while n:
  while x and x[-1][0]>=n:k,l,r=x.pop();heappush(h,(r-l,l,r))
  if h:s+=heappop(h)[1]
  n-=1
 return s+sum(r for*_,r in x+h)
for _ in'_'*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=map(int,i().split())
  if l>r:x+=(k,l,r),
  else:y+=(n-k,r,l),
 print(f(s(x))+f(s(y)))

Solution (Python):
import heapq

t = int(input())
for i in range(t):
    n = int(input())
    a1 = []
    a2 = []
    ans = 0
    for j in range(n):
        k, l, r = map(int, input().split())
        if l > r:
            a1.append([l - r, k])
            ans += l
        elif l < r:
            a2.append([r - l, n - k])
            ans += r
        else:
            ans += l
    a1.sort(key = lambda x: x[1])
    a2.sort(key = lambda x: x[1])
    num = 1
    num2 = 0
    num3 = 0
    queue = []
    heapq.heapify(queue)
    while num <= n:
        if num2 == len(a1):
            break
        else:
            while a1[num2][1] == num:
                heapq.heappush(queue, a1[num2])
                num2 += 1
                num3 += 1
                if num2 == len(a1):
                    break
            while num3 > num:
                temp = heapq.heappop(queue)
                ans -= temp[0]
                num3 -= 1
            else:
                num += 1
    num = 0
    num2 = 0
    num3 = 0
    queue = []
    heapq.heapify(queue)
    while num <= n:
        if num2 == len(a2):
            break
        else:
            while a2[num2][1] == num:
                heapq.heappush(queue, a2[num2])
                num2 += 1
                num3 += 1
                if num2 == len(a2):
                    break
            while num3 > num:
                temp = heapq.heappop(queue)
                ans -= temp[0]
                num3 -= 1
            else:
                num += 1
    print(ans)

Solution (Python):
from heapq import*
s=sorted
def f(x):
 s,n,*h=0,len(x)
 while n:
  while x and x[-1][0]>=n:k,l,r=x.pop();heappush(h,(r-l,l,r))
  if h:s+=heappop(h)[1]
  n-=1
 return s+sum(r for*_,r in x+h)
z=open(0).read().split()
i=1
while i<len(z):
 n,x,*y=int(z[i]),[];i+=1
 for k,l,r in zip(*[map(int,z[i:i+n*3])]*3):
  if l>r:x+=(k,l,r),
  else:y+=(n-k,r,l),
 print(f(s(x))+f(s(y)));i+=n*3

Solution (Python):
def main():
  from collections import deque
  import sys
  input = sys.stdin.readline
  from heapq import heapify,heappop,heappush
  T = int(input())
  for _ in range(T):
    N = int(input())
    KLR = [list(map(int,input().split())) for _ in range(N)]
    left = deque([])
    right = deque([])
    ans = 0
    for K,L,R in KLR:
      x = L - R
      if x==0:
        ans += L
      elif x>0:
        left.append([K,L,R])
        ans += R
      else:
        right.append([K+1,L,R])
        ans += L

    left = sorted(left)
    right = sorted(right,reverse=True)
      
    S = []
    heapify(S)
    x = 1
    i = 0
    length = len(left)
    while x<=N:
      while i<length:
        klr = left[i]
        if klr[0]==x:
          heappush(S,klr[1]-klr[2])
          i += 1
          
        else:
          break
      
      y = len(S) - x
      if y<=0:
        x += 1
        continue
      else:
        for _ in range(y):
          heappop(S)
          
    ans += sum(S)
    
    S = []
    heapify(S)
    x = N+1
    i = 0
    length = len(right)
    while x>=0:
      while i<length:
        klr = right[i]
        if klr[0]==x:
          heappush(S,klr[2]-klr[1])
          i += 1
 
        else:
          break
      
      y = len(S) + x - N - 1
      if y<=0:
        x -= 1
        continue
      else:
        for _ in range(y):
          heappop(S)    
    ans += sum(S)
    print(ans)
    
main()

Solution (Python):
from heapq import*
i=input
s=sorted
def f(x):
 s,n,*h=0,len(x)
 while n:
  while x and x[-1][0]>=n:k,l,r=x.pop();heappush(h,(r-l,l,r))
  if h:s+=heappop(h)[1]
  n-=1
 return s+sum(r for*_,r in x+h)
for _ in'_'*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=map(int,i().split())
  if l>r:x+=(k,l,r),
  else:y+=(n-k,r,l),
 print(f(s(x))+f(s(y)))

Solution (Python):
from heapq import*
i=input
s=sorted
def f(x):
 s,n,*h=0,len(x)
 while n:
  while x and x[-1][0]>=n:k,l,r=x.pop();heappush(h,(r-l,l,r))
  if h:s+=heappop(h)[1]
  n-=1
 return s+sum(r for _,_,r in x+h)
for _ in'_'*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=map(int,i().split())
  if l>r:x+=(k,l,r),
  else:y+=(n-k,r,l),
 print(f(s(x))+f(s(y)))

Solution (Python):
import heapq

def main2(l, n):
    ans = 0
    lis = []
    heapq.heapify(lis)

    for i in range(1, n):
        for j in l[i]:
            heapq.heappush(lis, j)
        while len(lis) > i:
            ans += heapq.heappop(lis)

    return ans

def main():
    from sys import stdin

    t = int(stdin.readline().strip())

    answer = []
    for _ in range(t):

        n = int(stdin.readline().strip())
        ans = 0
        l = [[] for _ in range(n+1)]
        r = [[] for _ in range(n+1)]

        for _ in range(n):
            i, j, k = map(int, stdin.readline().strip().split())
            if j > k:
                ans += j
                l[i].append(j-k)
            elif j < k:
                if i == n:
                    ans += j
                else:
                    ans += k
                    r[n-i].append(k-j)
            else:
                ans += j

        ans -= main2(l, n) + main2(r, n)
        answer.append(ans)

    for i in answer:
        print(i)

main()

Solution (Python):
from heapq import*
def solve(x):
    s,*h=0,
    for i in range(len(x),0,-1):
        while x and x[-1][0]>=i:
            k,l,r=x.pop()
            heappush(h,(r-l,l,r))
        if h:s+=heappop(h)[1]
    return s+sum(r for _,_,r in x+h)
for _ in range(int(input())):
    n=int(input())
    x,y=[],[]
    for _ in range(n):
        k,l,r=map(int,input().split())
        if l>r:x+=(k,l,r),
        else:y+=(n-k,r,l),
    print(solve(sorted(x))+solve(sorted(y)))

Solution (Python):
import heapq

def main2(l, n):
    ans = 0
    lis = []
    heapq.heapify(lis)

    for i in range(1, n):
        for j in l[i]:
            heapq.heappush(lis, j)
        while len(lis) > i:
            ans += heapq.heappop(lis)

    return ans

def main():
    from sys import stdin

    t = int(stdin.readline().strip())

    answer = []
    for _ in range(t):

        n = int(stdin.readline().strip())
        ans = 0
        l = [[] for _ in range(n+1)]
        r = [[] for _ in range(n+1)]

        for _ in range(n):
            i, j, k = map(int, stdin.readline().strip().split())
            if j > k:
                ans += j
                l[i].append(j-k)
            elif j < k:
                if i == n:
                    ans += j
                else:
                    ans += k
                    r[n-i].append(k-j)
            else:
                ans += j

        ans -= main2(l, n) + main2(r, n)
        answer.append(ans)

    for i in answer:
        print(i)

main()

Solution (Python):
import sys
from heapq import*
input=sys.stdin.buffer.readline
def solve():
    n=int(input())
    x,y=[],[]
    for _ in range(n):
        k,l,r=map(int,input().split())
        if l>r:
            x+=(k,l,r),
        else:
            y+=(n-k,r,l),
    x.sort()
    y.sort()
    s=0
    h=[]
    for i in range(len(x),0,-1):
        while x and x[-1][0]>=i:
            k,l,r=x.pop()
            heappush(h,(r-l,l,r))
        if h:s+=heappop(h)[1]
    s+=sum(r for _,_,r in x+h)
    h=[]
    for i in range(len(y),0,-1):
        while y and y[-1][0]>=i:
            k,l,r=y.pop()
            heappush(h,(r-l,l,r))
        if h:s+=heappop(h)[1]
    s+=sum(r for _,_,r in y+h)
    return s
t=int(input())
print('\n'.join(str(solve())for _ in range(t)))

Solution (Python):
import heapq

def main2(l, n):
    ans = 0
    lis = []
    heapq.heapify(lis)
    for i in range(1, n):
        for j in l[i]:
            heapq.heappush(lis, j)
        while len(lis) > i:
            ans += heapq.heappop(lis)
    return ans

def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    t = int(input())

    answer = []
    for _ in range(t):

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

        ans -= main2(l, n) + main2(r, n)
        answer.append(ans)

    for i in answer:
        print(i)

main()

Solution (Python):
import heapq

def main2(l, n):
    ans = 0
    lis = []
    heapq.heapify(lis)
    for i in range(1, n):
        for j in l[i]:
            heapq.heappush(lis, j)
        while len(lis) > i:
            ans += heapq.heappop(lis)
    return ans

def main():
    from sys import stdin
    def input():
        return stdin.readline().strip()

    t = int(input())

    answer = []
    for _ in range(t):

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

        ans -= main2(l, n) + main2(r, n)
        answer.append(ans)

    for i in answer:
        print(i)

main()

Solution (Python):
import sys
import heapq
sys.setrecursionlimit(10**8)
stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def naa(N): return [na() for _ in range(N)]


def ns(): return stdin.readline().rstrip()  


T = ni()

for _ in range(T):
    N = ni()
    ans = 0
    plus = []
    minus = []
    for _ in range(N):
        k, l, r = na()
        if l > r:
            plus.append([k, l-r])
            ans += r
        elif l < r:
            if N != k:
                minus.append([N-k, r-l])
            ans += l
        else:
            ans += l
    plus = sorted(plus, key=lambda x: x[0] * 10 ** 10 - x[1])
    minus = sorted(minus, key=lambda x: x[0] * 10 ** 10 - x[1])
    queue = []
    for p in plus:
        i, v = p 
        if len(queue) < i:
            heapq.heappush(queue, v)
        else:
            if queue[0] < v:
                heapq.heappushpop(queue, v)
    ans += sum(queue)
    queue = []
    for m in minus:
        i, v = m
        if len(queue) < i:
            heapq.heappush(queue, v)
        else:
            if queue[0] < v:
                heapq.heappushpop(queue, v)
    ans += sum(queue)
    print(ans)

Solution (Python):
import heapq

t = int(input())
for _ in range(t):
    n = int(input())
    l = [[] for i in range(n+1)]
    r = [[] for i in range(n+1)]
    ans = 0
    for i in range(n):
        a,b,c = map(int,input().split())
        if b > c:
            l[a].append(b-c)
            ans += c
        else:
            r[a].append(c-b)
            ans += b
    q = []
    for i, lx in enumerate(l):
        for x in lx:
            if len(q) < i:
                heapq.heappush(q,x)
            else:
                heapq.heappushpop(q,x)
    ans += sum(q)
    q = []
    for i,rx in enumerate(r[::-1][1:],1):
        for x in rx:
            if len(q) < i:
                heapq.heappush(q,x)
            else:
                heapq.heappushpop(q,x)
    ans += sum(q)
    print(ans)