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.buffer.readline

T = int(input())


def update_max(k,x):
    k += num_max-1
    seg_max[k] = x
    while k:
        k = (k-1)//2
        seg_max[k] = max(seg_max[k*2+1],seg_max[k*2+2])
    
def query_max(p,q):
    if q<=p:
        return ide_ele_max
    p += num_max-1
    q += num_max-2
    res=ide_ele_max
    while q-p>1:
        if p&1 == 0:
            res = max(res,seg_max[p])
        if q&1 == 1:
            res = max(res,seg_max[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = max(res,seg_max[p])
    else:
        res = max(max(res,seg_max[p]),seg_max[q])
    return res
def update_min(k,x):
    k += num_min-1
    seg_min[k] = x
    while k:
        k = (k-1)//2
        seg_min[k] = min(seg_min[k*2+1],seg_min[k*2+2])
def init_min(init_min_val):
    
    for i in range(n):
        seg_min[i+num_min-1]=init_min_val[i]    
    
    for i in range(num_min-2,-1,-1) :
        seg_min[i]=min(seg_min[2*i+1],seg_min[2*i+2])
def init_max(init_max_val):
    
    for i in range(n):
        seg_max[i+num_max-1]=init_max_val[i]    
    
    for i in range(num_max-2,-1,-1) :
        seg_max[i]=max(seg_max[2*i+1],seg_max[2*i+2]) 
def query_min(p,q):
    if q<=p:
        return ide_ele_min
    p += num_min-1
    q += num_min-2
    res=ide_ele_min
    while q-p>1:
        if p&1 == 0:
            res = min(res,seg_min[p])
        if q&1 == 1:
            res = min(res,seg_min[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,seg_min[p])
    else:
        res = min(min(res,seg_min[p]),seg_min[q])
    return res


ide_ele_max = -1

ide_ele_min = 10**10


dg = 10**6

for testcase in range(T):
    n = int(input())
    
    num_max =2**(n-1).bit_length()
    seg_max=[ide_ele_max]*2*num_max
    
    num_min =2**(n-1).bit_length()
    seg_min=[ide_ele_min]*2*num_min
    init_min(list(range(n)))
    init_max(list(range(n)))

    res = 0
    tank = []
    res = 0
    for i in range(n):
        K,L,R = map(int,input().split())
        K -= 1
        if L <= R:
            tank.append((R-L)*dg+K*2+1)
            res += L
        else:
            tank.append((L-R)*dg+K*2)
            res += R
    tank.sort(reverse = True)
    s = 0
    for e in tank:
        pt,amari = divmod(e,dg)
        idx,right = divmod(amari,2)
        if right == 0:
            kk = query_max(0,idx+1)
            if kk != -1:
                res += pt
                update_max(kk,-1)
        else:
            kk = query_min(idx+1,n)
            if kk != 10**10:
                res += pt
                update_min(kk,10**19)

    print(res)

Solution (Python):
from heapq import heappush, heappop
T = int(input())

for _ in range(T):
    N = int(input())
    arr1 = []
    arr2 = []
    for _ in range(N):
        K, L, R = list(map(int, input().split()))
        if L > R:
            arr1.append((K, L, R))
        else:
            arr2.append((N-K, R, L))

    arr1.sort()
    baseS = 0
    diffS = 0
    q = []
    length = 0
    for K, L, R in arr1:
        baseS += R
        diff = L - R
        heappush(q, diff)
        diffS += diff
        length += 1
        while length > K:
            d = heappop(q)
            diffS -= d
            length -= 1
    ans = baseS + diffS

    arr2.sort()
    baseS = 0
    diffS = 0
    q = []
    length = 0
    for K, L, R in arr2:
        baseS += R
        diff = L - R
        heappush(q, diff)
        diffS += diff
        length += 1
        while length > K:
            d = heappop(q)
            diffS -= d
            length -= 1
    ans += baseS + diffS
    print(ans)

Solution (Python):





import heapq

T = int(input())
for _ in range(T):
    N = int(input())
    frontCamel = []
    backCamel = []
    indifferentCamel = []
    Happiness = 0
    for _ in range(N):
        k,l,r = map(int,input().split())
        if l > r:
            frontCamel.append((k,l-r))
            Happiness += r
        elif r > l:
            backCamel.append((N-k,r-l))
            Happiness += l
        else:
            indifferentCamel.append((k,0))
            Happiness += l
    frontQ = []
    backQ = []
    frontCamel.sort(key = lambda x:x[0])
    backCamel.sort(key = lambda x:x[0])
    for Camel in frontCamel:
        if Camel[0] == 0:
            continue
        if Camel[0] > len(frontQ):
            heapq.heappush(frontQ,Camel[1])
        else:
            if frontQ[0] < Camel[1]:
                heapq.heapreplace(frontQ,Camel[1])
    for Camel in backCamel:
        if Camel[0] == 0:
            continue
        if Camel[0] > len(backQ):
            heapq.heappush(backQ,Camel[1])
        else:
            if backQ[0] < Camel[1]:
                heapq.heapreplace(backQ,Camel[1])
    Happiness += sum(frontQ)
    Happiness += sum(backQ)
    print(Happiness)

Solution (Python):
def examA():
    L, R, D = LI()
    ans = R//D - (L-1)//D
    print(ans)
    return

def examB():
    N = I()
    A = LI()
    ans = 0
    for i,a in enumerate(A):
        if i%2==0:
            if a%2==1:
                ans += 1
    print(ans)
    return

def examC():
    N = I()
    ans = [0]*N
    for x in range(1,101):
        for y in range(1,101):
            for z in range(1,101):
                cur = x**2 + y**2 + z**2 + x*y + y*z + x*z
                if cur<N+1:
                    ans[cur-1] += 1

    for v in ans:
        print(v)
    return

def examD():
    def popcnt0(n):
        c = 0
        for i in range(20):
            c += (n >> i) & 1
        return c
    def cnt(num):
        c = 0
        while(num>0):
            
            num %= popcnt0(num)
            c += 1
        return c
    N = I()
    X = SI()
    S_upper = [0]*N
    S_lower = [0]*N
    start_upper = 0
    start_lower = 0
    bit = 0
    ans = [0]*N
    for s in X:
        if s=="1":
            bit += 1
    if bit==1:
        b = 0
        for i in range(N):
            if X[i]=="1":
                ans[i] = 0
                b = i
            else:
                ans[i] = 1
        if b==N-1:
            for i in range(N-1):
                ans[i] += 1
        else:
            ans[-1] += 1
        for v in ans:
            print(v)
        return
    elif bit==0:
        for v in ans:
            print(1)
        return
    for i in range(N):
        S_upper[i] = pow(2,N-i-1,bit+1)
        S_lower[i] = pow(2,N-i-1,bit-1)
        if X[i]=="1":
            start_upper += S_upper[i]
            start_lower += S_lower[i]
            start_upper %= (bit+1)
            start_lower %= (bit-1)
    for i in range(N):
        if X[i]=="0":
            cur = (start_upper + S_upper[i]) % (bit+1)
            ans[i] = cnt(cur)+1
        else:
            cur = (start_lower - S_lower[i] + 2*(bit -1)) % (bit-1)
            ans[i] = cnt(cur)+1
        

    for v in ans:
        print(v)
    return

def examE():
    T = I()
    ans = [0]*T

    for t in range(T):
        N = I()
        KLR = [LI()for _ in range(N)]
        L = [[]for _ in range(N)]; R = [[]for _ in range(N)]
        for k,l,r in KLR:
            if l<r:
                ans[t] += l
                if k==N:
                    continue
                R[k].append(r-l)
            elif r<l:
                L[k-1].append(l-r)
                ans[t] += r
            else:
                ans[t] += l
        
        
        
        que = []
        for i in range(N)[::-1]:
            for l in L[i]:
                heappush(que,-l)
            if que:
                ans[t] += -heappop(que)
        que = []
        for i in range(N):
            for r in R[i]:
                heappush(que,-r)
            if que:
                ans[t] += -heappop(que)

    for v in ans:
        print(v)
    return

def examF():
    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(2*10**6)

if __name__ == '__main__':
    examE()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

Solution (Python):
import heapq

def main():
    T = int(input())
    for _ in range(T):
        N = int(input())
        KLR = [tuple(map(int, input().split())) for _ in range(N)]
        KLR.sort()
        H = []
        T = []
        s = 0
        for k, l, r in KLR:
            s += r
            if l - r >= 0:
                heapq.heappush(H, (l - r, k))
                while len(H) > k:
                    T.append(heapq.heappop(H))
            else:
                T.append((l - r, k))
        s += sum(l for l, k in H)
        H = []
        T.sort(key = lambda x: -x[1])
        for l, k in T:
            heapq.heappush(H, (-l, N - k))
            while len(H) > N - k:
                s -= heapq.heappop(H)[0]

        print(s)
main()

Solution (Python):
import sys
from heapq import heappush, heappop, heappushpop

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main(N, K, L, R):
    left = [[] for _ in range(N)]
    right = [[] for _ in range(N)]
    score = 0
    for k, l, r in zip(K, L, R):
        k -= 1
        if l < r:
            score += l
            right[k].append(r - l)
        else:
            score += r
            left[k].append(l - r)
    q = []
    for n, xs in enumerate(left, 1):
        for x in xs:
            if len(q) < n:
                heappush(q, x)
            else:
                heappushpop(q, x)
    score += sum(q)
    q = []
    for n, xs in enumerate(right[::-1][1:], 1):
        for x in xs:
            if len(q) < n:
                heappush(q, x)
            else:
                heappushpop(q, x)
    score += sum(q)
    return score

T = int(readline())
for _ in range(T):
    N = int(readline())
    K, L, R = [], [], []
    for _ in range(N):
        k, l, r = map(int, readline().split())
        K.append(k)
        L.append(l)
        R.append(r)
    print(main(N, K, L, R))

Solution (Python):
import sys
import heapq as hq

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n = ni()
    f = list()
    g = list()
    ans = 0
    for i in range(n):
        k, l, r = nm()
        if l > r:
            ans += r
            g.append((k, l-r))
        else:
            ans += l
            f.append((k+1, r-l))
    g.sort()
    f.sort(reverse=True)
    h = list()
    
    
    for k in range(len(g), 0, -1):
        while g and g[-1][0] >= k:
            _, c = g.pop()
            hq.heappush(h, -c)
        if h:
            ans -= hq.heappop(h)
    h = list()
    for k in range(len(g)+1, n+1):
        while f and f[-1][0] <= k:
            _, c = f.pop()
            hq.heappush(h, -c)
        if h:
            ans -= hq.heappop(h)
    print(ans)
    return

T = ni()
for _ in range(T):
    solve()

Solution (Python):
mod = 1000000007
eps = 10**-9


def main():
    import sys
    input = sys.stdin.buffer.readline

    class Bit:
        def __init__(self, n):
            self.size = n
            self.tree = [0] * (n + 1)

        def sum(self, i):
            s = 0
            while i > 0:
                s += self.tree[i]
                i -= i & -i
            return s

        def add(self, i, x):
            while i <= self.size:
                self.tree[i] += x
                i += i & -i

        def lower_bound(self, w):
            if w <= 0:
                return 0
            x = 0
            k = 1 << (self.size.bit_length() - 1)
            while k:
                if x + k <= self.size and self.tree[x + k] < w:
                    w -= self.tree[x + k]
                    x += k
                k >>= 1
            return x + 1

    for _ in range(int(input())):
        N = int(input())
        Llike = []
        Rlike = []
        ans = 0
        for _ in range(N):
            k, l, r = map(int, input().split())
            if l > r:
                Llike.append([l-r, k])
                ans += l
            elif r > l:
                if k == N:
                    ans += l
                else:
                    Rlike.append([r-l, N-k])
                    ans += r
            else:
                ans += r
        bitL = Bit(len(Llike))
        bitR = Bit(len(Rlike))
        Llike.sort(key=lambda x: x[0], reverse=True)
        Rlike.sort(key=lambda x: x[0], reverse=True)
        for i in range(len(Llike)):
            bitL.add(i+1, 1)
        for i in range(len(Rlike)):
            bitR.add(i+1, 1)
        for v, k in Llike:
            if k > len(Llike):
                k = len(Llike)
            u = bitL.sum(k)
            if u == 0:
                ans -= v
                j = bitL.lower_bound(bitL.sum(len(Llike)))
                bitL.add(j, -1)
            else:
                j = bitL.lower_bound(u)
                bitL.add(j, -1)
        for v, k in Rlike:
            if k > len(Rlike):
                k = len(Rlike)
            u = bitR.sum(k)
            if u == 0:
                ans -= v
                j = bitR.lower_bound(bitR.sum(len(Rlike)))
                bitR.add(j, -1)
            else:
                j = bitR.lower_bound(u)
                bitR.add(j, -1)
        print(ans)


if __name__ == '__main__':
    main()

Solution (Python):

TT = int(input())
import heapq

for loop in range(TT):

    N = int(input())

    L = []
    R = []

    abmax = 0

    for i in range(N):

        k,l,r = map(int,input().split())

        if l >= r:
            L.append( (k,l,r) )
            abmax += l
        else:
            R.append( (N-k,r,l) )
            abmax += r

    L.sort()
    R.sort()

    q = []
    for i in range(len(L)):

        k,nowc,nexc = L[i]
        heapq.heappush( q , nowc-nexc )

        while len(q) > k:
            tmp = heapq.heappop(q)
            abmax -= tmp

    q = []
    for i in range(len(R)):

        k,nowc,nexc = R[i]
        heapq.heappush( q , nowc-nexc )

        while len(q) > k:
            tmp = heapq.heappop(q)
            abmax -= tmp

    print (abmax)

Solution (Python):
import sys
input = sys.stdin.readline
import heapq as hp

Q = int(input())
Query = []
for _ in range(Q):
    N = int(input())
    KLR = [list(map(int, input().split())) for _ in range(N)]
    Query.append((N, KLR))

for N, KLR in Query:
    basic = 0
    Ls = [[] for _ in range(N)]
    Rs = [[] for _ in range(N)] 
    for k, l, r in KLR:
        if l > r:
            basic += r
            Ls[k-1].append(l-r)
        elif r > l:
            if k != N:
                basic += l
                Rs[k].append(r-l)
            else:
                basic += l
        else:
            basic += r
    
    ans = basic
    q1 = []
    for i in reversed(range(N)):
        for l in Ls[i]:
            hp.heappush(q1, -l)
        if q1:
            p = -hp.heappop(q1)
            ans += p
    
    q2 = []
    for i in range(N):
        for r in Rs[i]:
            hp.heappush(q2, -r)
        if q2:
            p = -hp.heappop(q2)
            ans += p
    
    print(ans)