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):
from heapq import heapify
from heapq import heappush as push
from heapq import heappop as pop
def solve():
  n=int(input())
  ans=0
  pos=[[] for _ in range(n)]
  neg=[[] for _ in range(n)]
  for _ in range(n):
    k,l,r=map(int,input().split())
    ans+=min(l,r)
    if l>r:
      pos[k-1].append(l-r)
    elif l<r and k<n:
      neg[k].append(r-l)
  q=[]
  heapify(q)
  for i in range(n):
    for j in pos[i]:
      push(q,j)
    while i+1<len(q):
      pop(q)
  while q:
    ans+=pop(q)
  for i in range(n-1,-1,-1):
    for j in neg[i]:
      push(q,j)
    while n-i<len(q):
      pop(q)
  while q:
    ans+=pop(q)
  print(ans)

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

if __name__=='__main__':
  main()

Solution (Python):

import sys
from heapq import heappush, heappop, heapify
from collections import deque
from collections import namedtuple
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


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


def main():
    T = INT()
    for t in range(T):
        solve()
    return

def solve():
    
    N = INT()
    left_camel = []
    right_camel = []
    camel = namedtuple("camel", "value, kth")
    ans = 0
    for k, l, r in ZIP(N):
        if l >= r:
            left_camel.append(camel(l-r, k))
            ans += r
        else:
            right_camel.append(camel(r-l, N-k))
            ans += l
    left_camel.sort(key=lambda x: x.kth)
    right_camel.sort(key=lambda x: x.kth)
    left_camel = deque(left_camel)
    right_camel = deque(right_camel)
    for camels in [left_camel, right_camel]:
        S = []
        while camels and camels[0].kth == 0:
            camels.popleft()
        for j in range(1, N+1):
            while camels and camels[0].kth == j:
                heappush(S, camels.popleft())
            while len(S) > j:
                heappop(S)
        while S:
            ans += heappop(S).value
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [-int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()
    DD = ((1,0),(0,1),(-1,0),(0,-1))

    T = NI()
    for _ in range(T):

        N = NI()
        top = []
        bot = []

        ans = 0
        for _ in range(N):
            k,l,r = LI()
            ans += max(l,r)
            if l < r:
                bot.append((N-k,r-l))
            else:
                top.append((k,l-r))

        top.sort()
        bot.sort()

        q = []
        for k,v in top:
            heapq.heappush(q,v)
            if len(q) > k:
                vd = heapq.heappop(q)
                ans -= vd

        q = []
        for k,v in bot:
            heapq.heappush(q,v)
            if len(q) > k:
                vd = heapq.heappop(q)
                ans -= vd

        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))



class OrderedSet:
    def __init__(self,n):
        self.c = {}
        self.r = {}
        
        self.a_sort = list(range(n))
        for i,a in enumerate(self.a_sort):
            self.c[a] = i+1
            self.r[i+1] = a
        self.size = len(self.c)
        self.tree = [0]*(self.size + 1)
        self.num = [0]*self.size
        self.all_count = 0  

    
    def _sum(self,index):
        s = 0
        while index:
            s += self.tree[index]
            index -= index & (-index)
        return s

    
    def insert(self,x,k=1):
        index = self.c[x]
        self.num[index-1] += k
        while index <= self.size:
            self.tree[index] += k
            index += index & (-index)
        self.all_count += k
    
    
    def erase(self,x,k=1):
        self.insert(x,k=-k)

    
    def count(self,x):
        return self.num[self.c[x]-1]

    
    def get_kth_bottom(self,k):
        if k <= 0:
            return None
        elif self.all_count < k:
            return None
        else:
            i = 0
            s = 0
            step = 1 << (self.size.bit_length() - 1)
            while step:
                if i+step <= self.size and s+self.tree[i+step] < k:
                    i += step
                    s += self.tree[i]
                step >>= 1
            return self.r[i+1]
    
    
    def get_kth_top(self,k):
        return self.get_kth_bottom(self.all_count-k+1)
    
    
    def lower_bound(self,x):
        if x in self.c.keys():
            p = self.c[x]-1
        else:
            p = bisect_left(self.a_sort,x)
        if p == 0:
            k = 1
        else:
            k = self._sum(p) + 1
        return self.get_kth_bottom(k)
    
    
    def upper_bound(self,x):
        if x in self.c.keys():
            p = self.c[x]
        else:
            p = bisect_right(self.a_sort,x)
        if p == 0:
            return None
        else:
            k = self._sum(p)
            return self.get_kth_bottom(k)

T = I()

ans = []
for _ in range(T):
    N = I()
    K,L,R = LIR(N,3)
    
    left = []    
    right = []   
    for i in range(N):
        large = max(L[i],R[i])
        small = min(L[i],R[i])
        gap = large-small
        if L[i] >= R[i]:
            left.append((gap,K[i]-1,large,small))
        else:
            right.append((gap,K[i],large,small))

    left.sort(key=lambda x:x[0], reverse=True)
    right.sort(key=lambda x:x[0], reverse=True)

    ordset = OrderedSet(N)
    ans_t = 0

    
    for i in range(N):
        ordset.insert(i)

    for i in range(len(left)):
        p = ordset.upper_bound(left[i][1])
        if p is None:
            p2 = ordset.upper_bound(len(left)-1)
            ordset.erase(p2)
            ans_t += left[i][3]
        elif p >= len(left):
            p2 = ordset.upper_bound(len(left)-1)
            ordset.erase(p2)
            ans_t += left[i][2]            
        else:
            ordset.erase(p)
            ans_t += left[i][2]

    for i in range(len(right)):
        p = ordset.lower_bound(right[i][1])
        if p is None:
            p2 = ordset.lower_bound(len(left))
            ordset.erase(p2)
            ans_t += right[i][3]
        else:
            ordset.erase(p)
            ans_t += right[i][2]
    
    ans.append(ans_t)

for ans_t in ans:
    print(ans_t)

Solution (Python):
from heapq import heapify,heappush,heappop

T = int(input())
for _ in range(T):
  N = int(input())
  base = 0
  A = []
  C = []
  B = [0 for _ in range(N)]
  Q = []
  S = []
  for i in range(N):
    K, L, R = map(int,input().split()) 
    tmp = min(L, R)
    K -= 1
    if L > R:
      A.append((K,L-R))
    if R >= L:
      if K < N - 1:
        C.append((N-2-K,R-L))
    base += tmp
  A.sort(reverse = True)
  C.sort(reverse = True)
  
  
  
  for i in range(N):
    if len(A) == 0:
      break
    while A[-1][0] == i:
      a = A[-1][1] 
      A.pop()
      heappush(Q, a)
      if len(A) == 0:
        break
    while i+1 < len(Q):
      heappop(Q)
      if len(Q) == 0:
        break
  
  for i in range(N):
    if len(C) == 0:
      break
    while C[-1][0] == i:
      a = C[-1][1] 
      C.pop()
      heappush(S, a)
      if len(C) == 0:
        break
    while i+1 < len(S):
      heappop(S)
      if len(S) == 0:
        break
      
  print(base + sum(Q) + sum(S))
     
  """
  l = 0
  r = N-1
  for a in A:
    if a[2] == 0:
      if l < a[0]:
        l += 1
        base += a[1] 
    else:
      if r >= N-a[0]:
        r -= 1
        base += a[1]
  print(base)
  """

Solution (Python):

import sys
from heapq import heappush, heappop, heapify
from collections import deque
sys.setrecursionlimit(10**8)
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return [LIST() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]


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


def main():
    T = INT()
    for t in range(T):
        solve()
    return

def solve():
    
    N = INT()
    left_camel = []
    right_camel = []
    ans = 0
    for k, l, r in ZIP(N):
        if l >= r:
            left_camel.append((l-r, k))
            ans += r
        else:
            right_camel.append((r-l, N-k))
            ans += l
    left_camel.sort(key=lambda x: x[1])
    right_camel.sort(key=lambda x: x[1])
    left_camel = deque(left_camel)
    right_camel = deque(right_camel)
    
    for camels in [left_camel, right_camel]:
        S = []
        while len(camels) > 0 and camels[0][1] == 0:
            camels.popleft()
        for j in range(1, N+1):
            while len(camels) > 0 and camels[0][1] == j:
                heappush(S, camels.popleft())
            while len(S) > j:
                heappop(S)
        while S:
            ans += heappop(S)[0]
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import heapq

T = int(input())
Ns = []
cases = []*T
for i in range(T):
    Ns.append(int(input()))
    cases.append([list(map(int, input().split())) for _ in range(Ns[-1])])

for i in range(T):
    answer = 0
    N = Ns[i]
    case = cases[i]
    
    sa = [case[j][2]-case[j][1] for j in range(N)]
    pluss = []
    minuss = []
    for j in range(N):
        if sa[j] >= 0:
            pluss.append([case[j][0],case[j][1],case[j][2],sa[j]])
        else:
            minuss.append([case[j][0],case[j][1],case[j][2],sa[j]])
    pluss = sorted(pluss)
    minuss = sorted(minuss,reverse = True)
    hq = []
    checking = 0
    for j in range(N-len(pluss),N):
        if checking < len(pluss):
            while j > pluss[checking][0]-1:
                heapq.heappush(hq, [-pluss[checking][3],pluss[checking][1],pluss[checking][2],pluss[checking][0]])
                checking+=1
                if checking >= len(pluss):
                    break
        if len(hq)>0:
            temp = heapq.heappop(hq)
            answer += temp[2]

    for j in range(checking,len(pluss)):
        heapq.heappush(hq, [-pluss[j][3],pluss[j][1],pluss[j][2],pluss[j][0]])
        
    for j in range(len(hq)):
        temp = heapq.heappop(hq)
        answer += temp[1]

    hq = []
    checking = 0
    for j in range(len(minuss)-1,-1,-1):
        if checking < len(minuss):
            while j <= minuss[checking][0]-1:
                heapq.heappush(hq, [minuss[checking][3],minuss[checking][1],minuss[checking][2],minuss[checking][0]])
                checking+=1
                if checking >= len(minuss):
                    break
        if len(hq)>0:
            temp = heapq.heappop(hq)
            answer += temp[1]

    for j in range(checking, len(minuss)):
                    heapq.heappush(hq, [minuss[j][3],minuss[j][1],minuss[j][2],minuss[j][0]])

    for j in range(len(hq)):
        temp = heapq.heappop(hq)
        answer += temp[2]
    print(answer)

Solution (Python):
import sys
import heapq
hpush = heapq.heappush
hpop = heapq.heappop
input = sys.stdin.readline
for _ in range(int(input())):
  N = int(input())
  a = []
  mnsm = 0
  table = [[] for _ in range(N + 1)]
  ls = 0
  for _ in range(N):
    K, L, R = map(int, input().split())
    mnsm += min(L, R)
    a.append((K, L, R))
    if L >= R: table[K - 1].append((L, R))
    else: table[K].append((L, R))
    ls += L >= R
  h = []
  hh = []
  res = 0
  for i in range(N):
    for L, R in table[i]:
      if L >= R:
        hpush(h, L - R)
        res += L - R
    while len(h) > i + 1: res -= max(0, hpop(h))
  for i in range(N, -1, -1):
    for L, R in table[i]:
      if R > L:
        hpush(hh, R - L)
        res += R - L
    while len(hh) > N - i:
      res -= max(0, hpop(hh))
  print(mnsm + res)

Solution (Python):
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappush, heappop
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def main():
    from builtins import int, map
    N = int(input())
    total = 0
    L, R = [], []
    for _ in range(N):
        k, l, r = map(int, input().split())
        if l >= r:
            
            L.append((k, l, r))
            total += l
        else:
            
            R.append((N - k, r, l))
            total += r

    
    L.sort()
    R.sort()

    queue = []
    for i in range(len(L)):
        k, ai, bi = L[i]
        heappush(queue, ai - bi)
        
        while len(queue) > k:
            value = heappop(queue)
            total -= value
            
    queue = []
    for i in range(len(R)):
        k, ai, bi = R[i]
        heappush(queue, ai - bi)
        
        while len(queue) > k:
            value = heappop(queue)
            total -= value

    print(total)


if __name__ == '__main__':
    t = int(input())
    while t > 0:
        t -= 1
        main()

Solution (Python):
from sys import stdin
from sys import setrecursionlimit
from collections import Counter, deque, defaultdict
from heapq import heapify, heappush, heappop
from math import floor, ceil
from bisect import bisect_left
from itertools import combinations
setrecursionlimit(100000)

INF = int(1e10)
MOD = int(1e9 + 7)

def main():
    from builtins import int, map
    N = int(input())
    total = 0
    L, R = [], []
    for _ in range(N):
        k, l, r = map(int, input().split())
        if l >= r:
            
            L.append((k, l, r))
            total += l
        else:
            
            R.append((N - k, r, l))
            total += r

    
    L.sort()
    R.sort()

    queue = []
    for i in range(len(L)):
        k, ai, bi = L[i]
        heappush(queue, ai - bi)
        
        while len(queue) > k:
            value = heappop(queue)
            total -= value
            
    queue = []
    for i in range(len(R)):
        k, ai, bi = R[i]
        heappush(queue, ai - bi)
        
        while len(queue) > k:
            value = heappop(queue)
            total -= value

    print(total)


if __name__ == '__main__':
    t = int(input())
    while t > 0:
        t -= 1
        main()

Solution (Python):
import sys
sys.setrecursionlimit(700000)

def s_in():
    return input()

def n_in():
    return int(input())

def l_in():
    return list(map(int, input().split()))

from heapq import heappush, heappop

t = n_in()

for _ in range(t):
    n = n_in()

    sheeps = []
    for i in range(n):
        k,l,r = l_in()
        sheeps.append((i,k-1,l,r))


    res = 0
    base = 0

    memo = []
    for i in range(n):
        memo.append(set())

    base = 0
    for i,k,l,r in filter(lambda x: x[2] > x[3], sheeps):
        memo[k].add(i)
        base += r

    res += base

    q = []
        
    for pos in range(n):
        for s in memo[pos]:
            _,k,l,r = sheeps[s]
            heappush(q, (l-r, s))

        while len(q) > pos+1:
            heappop(q)

    for delta, i in q:
        res += delta

        
    memo = [set() for _ in range(n+1)]

    base = 0
    for i,k,l,r in filter(lambda x: x[2] <= x[3], sheeps):
        memo[k+1].add(i)
        base += l

    res += base

    q = []
        
    for pos in reversed(range(n)):
        for s in memo[pos]:
            _,k,l,r = sheeps[s]
            heappush(q, (r-l, s))

        while len(q) > n-pos:
            heappop(q)
    for delta, i in q:
        res += delta

    print(res)

Solution (Python):
def main():
    from collections import defaultdict
    from heapq import heappop, heappush

    def greedy(L):
        ret = 0
        q = []
        for k, gain in L:
            for g in gain:
                ret += g
                heappush(q, g)
            while len(q) > k:
                g = heappop(q)
                ret -= g
        return ret

    for _ in [0]*int(input()):
        N = int(input())

        ans = 0
        pos = defaultdict(list)
        neg = defaultdict(list)
        for _ in range(N):
            K, L, R = map(int, input().split())
            if L > R:
                ans += R
                pos[K].append(L-R)
            elif L < R:
                ans += L
                neg[N-K].append(R-L)
            else:
                ans += L

        pos = sorted(pos.items())
        neg = sorted(neg.items())
        ans += greedy(pos)
        ans += greedy(neg)

        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
from heapq import *
input = sys.stdin.readline

def get_happiness(camels):
    camels.sort(reverse=True)
    N = len(camels)
    ret = 0

    hq = []
    for i in range(1, N + 1):
        while camels and camels[-1][0] == i:
            _, diff = camels.pop()
            heappush(hq, diff)
        while len(hq) > i:
            heappop(hq)

    while camels:
        _, diff = camels.pop()
        ret += diff

    ret += sum(hq)

    return ret


def solution():
    N = int(input())
    left_camels = []
    right_camels = []
    left_sum = 0
    right_sum = 0
    for i in range(N):
        K, L, R = map(int, input().split())
        if L >= R:
            left_sum += R
            left_camels.append((K, L - R))
        else:
            right_sum += L
            if K == N: continue
            right_camels.append((N - K, R - L))
    answer = 0
    answer += left_sum + get_happiness(left_camels)
    answer += right_sum + get_happiness(right_camels)
    print(answer)

if __name__ == "__main__":
    T = int(input())
    for _ in range(T):
        solution()

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

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

Solution (Python):
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 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:h=[];s+=sum(heappush(h,l-r)or l-(k<len(h)and heappop(h))for k,l,r in sorted(x))
 print(s)

Solution (Python):
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 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:
  h=[]
  for k,l,r in sorted(x):heappush(h,l-r);s+=l-(k<len(h)and heappop(h))
 print(s)

Solution (Python):
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 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:
  h=[]
  for k,l,r in sorted(x):s+=l;heappush(h,l-r);s-=k<len(h)and heappop(h)
 print(s)

Solution (Python):
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 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:
  h=[]
  for k,l,r in sorted(x):
   s+=l;heappush(h,l-r)
   if len(h)>k:s-=heappop(h)
 print(s)

Solution (Python):
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 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:
  h=[]
  for k,l,r in sorted(x):
   s+=r
   if k:s+=l-r;heappush(h,l-r)
   if len(h)>k:s-=heappop(h)
 print(s)

Solution (Python):
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 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();h=[]
  for k,l,r in x:
   s+=r
   if k:s+=l-r;heappush(h,l-r)
   if len(h)>k:s-=heappop(h)
 print(s)

Solution (Python):




from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 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();h=[]
  for k,l,r in x:
   if k:s+=l;heappush(h,l-r)
   else:s+=r
   if len(h)>k:s-=heappop(h)
 print(s)

Solution (Python):




from heapq import*
i=input
for s in[0]*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]]
 for x in x,y:
  x.sort();h=[]
  for k,l,r in x:
   if k:s+=l;heappush(h,l-r)
   else:s+=r
   if len(h)>k:s-=heappop(h)
 print(s)

Solution (Python):




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

Solution (Python):




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

Solution (Python):
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 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=len(x);h=[(0,0)]*n*2
  while h:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   s+=heappop(h)[~(n>0)];n-=1
 print(s)

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)












class Segtree:
    

    

    
    
    

    

    def __init__(s,l,unit,oper):
        s.unit = unit
        s.oper = oper
        s.n = 1
        while s.n<l:
            s.n *= 2
        s.ary = [s.unit for i in range(2*s.n-1)]

    def get(s,i):
        return s.ary[i+s.n-1]

    def set(s,i,v):
        k = i+s.n-1
        s.ary[k] = v
        while k>0:
            k = (k-1)//2
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def setary(s,a):
        for i,v in enumerate(a):
            s.ary[i+s.n-1] = v
        for k in range(s.n-2,-1,-1):
            s.ary[k] = s.oper( \
                        s.ary[2*k+1], s.ary[2*k+2])

    def query(s,x,y):
        l = x+s.n-1
        r = y+s.n-1
        res = s.unit
        while l<r:
            if not l%2:
                res = s.oper(res,s.ary[l])
                l += 1
            if not r%2:
                r -= 1
                res = s.oper(res,s.ary[r])
            l >>= 1
            r >>= 1
        return res



t = inn()
for tt in range(t):
    
    n = inn()
    klr = []
    nl = 0
    for i in range(n):
        k,l,r = inm()
        klr.append((abs(l-r),(-k if l>r else -(n+1-k)),i,k,l,r))
        if l>r:
            nl += 1
    klrc = [z for z in klr]
    klr.sort(reverse=True)
    h = {}
    tol = Segtree(n,-1,lambda x,y: max(x,y))
    tor = Segtree(n,n+1,lambda x,y: min(x,y))
    tol.setary(list(range(n)))
    tor.setary(list(range(n)))
    for j in range(n):
        v,w,i,k,l,r = klr[j]
        if k==n:
            continue
        if l>r:
            x = min(nl-1,k-1)
            m = tol.query(0,x+1)
            if m<0:
                continue
            tol.set(m,-1)
            h[m] = i
        else:
            x = max(nl,k)
            m = tor.query(x,n)
            if m>n:
                continue
            tor.set(m,n+1)
            h[m] = i
        
    
    put = {}
    for x in h:
        put[h[x]] = 1
    top = 0
    for i in range(n):
        if i in put:
            continue
        while top in h:
            top += 1
        h[top] = i
    
    rev = [-1]*n
    sm = 0
    for i in range(n):
        j = h[i]
        v,w,ii,k,l,r = klrc[j]
        sm += l if i<=k-1 else r
        
    print(sm)

Solution (Python):
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 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 h or x:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[~(n>0)]
   n-=1
 print(s)

Solution (Python):
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 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 h or x:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[2-(n>0)]
   n-=1
 print(s)

Solution (Python):
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 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:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
   n-=1
  for*_,r in x+h:s+=r
 print(s)

Solution (Python):
from heapq import*
i=input
for*x,_ in'_'*int(i()):
 n,s,*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:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
   n-=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=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:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
   n-=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=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:
   while[[n,0,0]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
   n-=1
  for*_,r in x+h:s+=r
 print(s)

Solution (Python):
import heapq
for _ in range(int(input())):
    N=int(input())
    ListL=[[] for _ in range(N)]
    ListR=[[] for _ in range(N)]
    ans=0
    for _ in range(N):
        k,l,r=map(int,input().split())
        ans+=min(l,r)
        if l>=r:
            ListL[k-1].append(abs(l-r))
        else:
            ListR[k-1].append(abs(l-r))
    S=[]
    for n,L in enumerate(ListL,1):
        for l in L:
            if len(S)<n:
                heapq.heappush(S,l)
            else:
                heapq.heappushpop(S,l) 
    ans+=sum(S)
    S=[]
    for n,L in enumerate(ListR[::-1][1:],1):
        for l in L:
            if len(S)<n:
                heapq.heappush(S,l)
            else:
                heapq.heappushpop(S,l) 
    ans+=sum(S)

    print(ans)

Solution (Python):
import heapq

T = int(input())

for _ in range(T):
  N = int(input())
  rlt = 0
  dicl = {}
  dicr = {}
  Ls = []
  Rs = []
  mkl = 0
  mkr = 0
  for i in range(1,N+1):
    k, l, r = map(int, input().split())
    rlt += min(l, r)
    if l > r:
      if k not in dicl:
        dicl[k] = [l-r]
      else:
        dicl[k].append(l-r)
      mkl = max(mkl, k)
    else:
      if N-k not in dicr:
        dicr[N-k] = [r-l]
      else:
        dicr[N-k].append(r-l)
      mkr = max(mkr, N-k)

  for i in range(1,mkl+1):
    if i in dicl:
      for j in dicl[i]:
        heapq.heappush(Ls, j)
        rlt += j
    while len(Ls) > i:
      t = heapq.heappop(Ls)
      rlt -= t
  for i in range(1,mkr+1):
    if i in dicr:
      for j in dicr[i]:
        heapq.heappush(Rs, j)
        rlt += j
    while len(Rs) > i:
      t = heapq.heappop(Rs)
      rlt -= t
      
  print(rlt)

Solution (Python):
from heapq import*
i=input
c=int(i())
while c:
 n=m=int(i());s,x,*y=0,[]
 while m:k,l,r=t=[*map(int,i().split())];x+=[t]*(l>r);y+=[(n-k,r,l)]*(l<=r);m-=1
 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);c-=1

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import heapq

def _solve(N, _list):
    n = len(_list)
    
    _list.sort(key=lambda x: x[0])
    
    
    base_score = sum([x[2] for x in _list])

    ni = 0
    S = []
    for j in range(N+1):
        
        while ni < n and _list[ni][0] == j:
            _, L, R = _list[ni]
            heapq.heappush(S, L - R)
            ni += 1
        
        while len(S) > j:
            heapq.heappop(S)

    return base_score + sum(S)

def solve(N, KLR):
    BigL = [] 
    BigR = [] 

    for i in range(N):
        K, L, R = KLR[3*i], KLR[3*i+1], KLR[3*i+2]
        
        if L < R:
            
            
            BigR.append((N-K, R, L))
        else:
            
            BigL.append((K, L, R))

    return _solve(N, BigL) + _solve(N, BigR)
        
def main():
    T, *_all = map(int, read().split())
    n = 0

    ans = []
    for _ in range(T):
        N = _all[n]
        KLR = _all[n+1:n+1+3*N]
        ans.append(solve(N, KLR))
        n += 1 + 3*N

    print(*ans, sep='\n')

if __name__ == '__main__':
    main()