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 heapq as hp


t=int(input())
for i in range(t):
    n=int(input())

    lef=[[] for i in range(n+1)]
    rig=[[] for i in range(n+1)]
    a=[]
    hp.heapify(a)
    ans=0
    lefcnt=0

    for i in range(n):
        k,l,r=map(int,input().split())
        if(l>=r):
            ans+=r
            lefcnt+=1
            tmp=l-r
            lef[k].append(tmp)
        else:
            ans+=l
            tmp=r-l
            rig[n-k].append(tmp)
    for i in range(n,lefcnt,-1):
        for j in lef[i]:
            hp.heappush(a,-j)           
    for i in range(lefcnt,0,-1):
        for j in lef[i]:
            hp.heappush(a,-j)
        if(a):
            tmp=hp.heappop(a)*(-1)
            ans+=tmp

    a=[]
    hp.heapify(a)
    for i in range(n,n-lefcnt,-1):
        for j in rig[i]:
            hp.heappush(a,-j)    
    for i in range(n-lefcnt,0,-1):
        for j in rig[i]:
            hp.heappush(a,-j)
        if(a):
            tmp=hp.heappop(a)*(-1)
            ans+=tmp
    print(ans)

Solution (Python):
import heapq
from collections import defaultdict


def solve(N, klrs):
    
    
    
    
    
    
    left_camels, right_camels = defaultdict(list), defaultdict(list)
    for i, (k, l, r) in enumerate(klrs):
        if l > r:
            left_camels[k].append(i)
        elif l < r:
            right_camels[k + 1].append(i)
    
    que = []
    for k in range(N):
        for i in left_camels[k]:
            _, l, r = klrs[i]
            heapq.heappush(que, l - r)
        while len(que) > k + 1:
            heapq.heappop(que)
    p_1 = 0
    while len(que) > 0:
        p_1 += heapq.heappop(que)    
    
    que = []
    for k in range(N - 1, -1, -1):
        for i in right_camels[k]:
            _, l, r = klrs[i]
            heapq.heappush(que, r - l)
        while len(que) > N - k:
            heapq.heappop(que)
    p_2 = 0
    while len(que) > 0:
        p_2 += heapq.heappop(que)
    return p_1 + p_2 + sum(min(l, r) for _, l, r in klrs)


def main():
    T = int(input())
    ans = [0] * T
    for t in range(T):
        N = int(input())
        klrs = list()
        for _ in range(N):
            k, l, r = map(int, input().split())
            klrs.append([k - 1, l, r])
        ans[t] = solve(N, klrs)
    for a in ans:
        print(a)


if __name__ == '__main__':
    main()

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    T=I()
    import heapq
    
    def calc(X):
        
        hq=[]
        heapq.heapify(hq)
        X.sort(reverse=True)
        N2=len(X)
        cur=0
        temp=0
        for i in range(N2-1,-1,-1):
            while cur<=N2-1:
                k=X[cur][0]
                if k>i:
                    heapq.heappush(hq,-1*X[cur][1])
                    cur+=1
                else:
                    break
            if len(hq)!=0:
                a=heapq.heappop(hq)
                temp+=-1*a
                
        
        return temp 
    
    
    for _ in range(T):
        
        N=I()
        ans=0
        L=[]
        R=[]
        for i in range(N):
            K,l,r=MI()
            if l>=r:
                ans+=r
                L.append((K,l-r))
            else:
                ans+=l
                R.append((N-K,r-l))
                
        ans+=calc(L)
        ans+=calc(R)
        print(ans)
        
        
        

main()

Solution (Python):
from bisect import *
from collections import defaultdict
def solve():
  T = int(input())
  ans = [0]*T
  for t in range(T):
    N = int(input())
    left = defaultdict(lambda: [])
    right = defaultdict(lambda: [])
    for i in range(N):
      k,l,r = map(int, input().split())
      if k==N:
        ans[t] += l
      else:
        if l>r:
          insort_right(left[k],l-r)
        elif l<r:
          insort_right(right[k+1],r-l)
        ans[t] += min(l,r)
    lis = []
    for i in range(N,0,-1):
      for l in left[i]:
        insort_right(lis,l)
      if len(lis):
        ans[t] += lis.pop(-1)
    lis = []
    for i in range(2,N+1):
      for r in right[i]:
        insort_right(lis,r)
      if len(lis):
        ans[t] += lis.pop(-1)
  return ans
print(*solve(),sep='\n')

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

for _ in range(int(input())):
    N = int(input())
    ans = 0
    dl = defaultdict(list)
    dr = defaultdict(list)
    
    for _ in range(N):
        K, L, R = map(int, input().split())
        m = min(L, R)
        ans += m
        
        if L==m:
            dr[K+1].append(R-m)
        else:
            dl[K].append(L-m)
        
    pq = []
    
    for i in range(N, 0, -1):
        for v in dl[i]:
            heappush(pq, -v)
        
        if len(pq)>0:
            ans += -heappop(pq)
    
    pq = []
    
    for i in range(1, N+1):
        for v in dr[i]:
            heappush(pq, -v)
        
        if len(pq)>0:
            ans += -heappop(pq)
    
    print(ans)

Solution (Python):
import heapq
def solve():
  N = int(input())
  ans = 0
  left,right = [ [] for i in range(N) ],[ [] for i in range(N) ]
  for _ in range(N):
    k,l,r = map(int,input().split())
    ans += min(l,r)
    if l>r:
      left[k-1].append(l-r)
    else:
      if k >= N: continue
      right[k].append(r-l)

  
  pq = []
  for i in range(N-1,-1,-1):
    for l in left[i]:
      heapq.heappush(pq,-l)
    if pq:
      ans += -heapq.heappop(pq)

  
  pq = []
  for i in range(N):
    for r in right[i]:
      heapq.heappush(pq,-r)
    if pq:
      ans += -heapq.heappop(pq)

  print(ans)

for i in range(int(input())):
  solve()

Solution (Python):
import sys
import heapq
def input(): return sys.stdin.readline().rstrip()

def culc(li):
    li.sort(key=lambda x: x[1])
    h=[]
    for i in li:
        if len(h) >= i[1]:
            heapq.heappushpop(h, i[0])
        else:
            heapq.heappush(h, i[0])
    return sum(h)

def main():
    T=int(input())
    for _ in range(T):
        n=int(input())
        mae=[]
        ushiro=[]
        kijun=0
        for _ in range(n):
            k,l,r=map(int, input().split())
            if l>r:
                mae.append([l-r,k])
            else:
                ushiro.append([r-l,n-k])
            kijun+=min(l,r)
        print(culc(mae)+culc(ushiro)+kijun)
                    



if __name__ == '__main__':
    main()

Solution (Python):
from heapq import heapify, heappop, heappush
Ncase = int(input())
for case in range(Ncase):
  N = int(input())
  ans = 0
  Left = [];Right = []
  for i in range(N):
    K,L,R = map(int,input().split())
    if L > R:
      Left.append((K-1,L-R))
      ans += R
    elif R > L:
      if K != N: 
        Right.append((N-1-K,R-L))
      ans += L
    else:
      ans += L
  Left.sort(reverse=True);Right.sort(reverse=True) 
  
  now = 0
  PQ = []
  for loc in reversed(range(N)):
    
    while now < len(Left) and Left[now][0] == loc:
      heappush(PQ,-Left[now][1])
      now += 1
      if now >= len(Left):
        break
    if PQ:
      plus = -heappop(PQ)
      ans += plus
  
  now = 0
  PQ = []
  for loc in reversed(range(N)):
    while now < len(Right) and Right[now][0] == loc:
      heappush(PQ,-Right[now][1])
      now += 1
      if now >= len(Right):
        break
    if PQ:
      plus = -heappop(PQ)
      ans += plus
  print(ans)

Solution (Python):


from heapq import heappop, heappush
import sys
input = sys.stdin.readline

def resolve():
    T = int(input())
    for _ in range(T):
        N = int(input())
        ans = 0
        camels0 = [[] for _ in range (N)]
        camels1 = [[] for _ in range (N)]
        for _ in range(N):
            K,L,R = map(int, input().split())
            if L>R:
                camels0[K-1].append(L-R)
            elif L<R and K<N:
                camels1[N-K-1].append(R-L)
            ans += min(L,R)
        
        H = []
        for i in range(N):
            for j in camels0[i]:
                heappush(H,j)
            while len(H) > i+1:
                heappop(H)
        ans += sum(H)
        H = []
        for i in range(N):
            for j in camels1[i]:
                heappush(H,j)
            while len(H) > i+1:
                heappop(H)
        ans += sum(H)
        print(ans)
resolve()

Solution (Python):
import heapq
t = int(input())
for _ in range(t):
    n = int(input())
    klr = [tuple(map(int, input().split())) for _ in range(n)]
    klr.sort()
    
    left = [[]for _ in range(n)]
    right = [[]for _ in range(n)]
    score = 0
    for K,L,R in klr:
        if K!=n:
            if L<R:
                score+=L
                right[n-K-1].append(R-L)
            elif R<L:
                score+=R
                left[K-1].append(L-R)
            else:
                score+=L
        else:
            score+=L
    
    def calc(ls):
        n = len(ls)
        use = []
        retval = 0
        for i in reversed(range(n)):
            for x in ls[i]:
                heapq.heappush(use, -x)
            if use:
                retval-=heapq.heappop(use)
        return retval
    score+=calc(left)
    score+=calc(right)
    print(score)

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


T = int(input())
for t in range(T):
    N = int(input())
    left, right = [], []
    ans = 0
    for i in range(N):
        K, L, R = map(int, sys.stdin.readline().split())
        if L > R:
            ans += L
            left.append((K, L - R))
        elif L < R:
            ans += R
            right.append((K, R - L))
        else:
            ans += L
    
    pool = []
    pos = 1
    left.sort()
    cur = 0
    while cur < len(left):
        while cur < len(left) and left[cur][0] == pos:
            k, d = left[cur]
            heappush(pool, d)
            cur += 1
        while len(pool) > pos:
            d = heappop(pool)
            ans -= d
        pos += 1
            
    
    pool = []
    pos = N
    right.sort(reverse=True)
    cur = 0
    while cur < len(right):
        while cur < len(right) and right[cur][0] == pos:
            k, d = right[cur]
            heappush(pool, d)
            cur += 1
        while len(pool) > N - pos:
            d = heappop(pool)
            ans -= d
        pos -= 1

    print(ans)

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

ans_l = []
T = int(input())
for t in range(T):
    N = int(input())
    left, right = [], []
    ans = 0
    for i in range(N):
        K, L, R = map(int, sys.stdin.readline().split())
        if L > R:
            ans += L
            left.append((K, L - R))
        elif L < R:
            ans += R
            right.append((K, R - L))
        else:
            ans += L
    
    pool = []
    pos = 1
    left.sort()
    cur = 0
    while cur < len(left):
        while cur < len(left) and left[cur][0] == pos:
            k, d = left[cur]
            heappush(pool, d)
            cur += 1
        while len(pool) > pos:
            d = heappop(pool)
            ans -= d
        pos += 1
            
    
    pool = []
    pos = N
    right.sort(reverse=True)
    cur = 0
    while cur < len(right):
        while cur < len(right) and right[cur][0] == pos:
            k, d = right[cur]
            heappush(pool, d)
            cur += 1
        while len(pool) > N - pos:
            d = heappop(pool)
            ans -= d
        pos -= 1

    ans_l.append(ans)


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

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

ans_l = []
T = int(input())
for t in range(T):
    ans = 0
    N = int(input())
    left = []
    right = []
    neutral = []
    for i in range(N):
        K, L, R = map(int, sys.stdin.readline().split())
        if L > R:
            heappush(left, (K, L - R, L, R))
        elif L < R:
            heappush(right, (-K, R - L, L, R))
        else:
            ans += L
    
    pool = []
    pos = 1
    while left:
        while left and left[0][0] == pos:
            k, d, l, r = heappop(left)
            heappush(pool, (d, l, r))
        while len(pool) > pos:
            d, l, r = heappop(pool)
            ans += r
        pos += 1
    while pool:
        d, l, r = heappop(pool)
        ans += l
            
    
    pool = []
    pos = N
    while right:
        while right and right[0][0] == -pos:
            k, d, l, r = heappop(right)
            heappush(pool, (d, l, r))
        while len(pool) > N - pos:
            d, l, r = heappop(pool)
            ans += l
        pos -= 1
    while pool:
        d, l, r = heappop(pool)
        ans += r

    ans_l.append(ans)


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

Solution (Python):
import heapq

def g(LS):
    Q = [];
    QLen = 0
    SC = 0

    for k,sc in sorted(LS):
        heapq.heappush(Q, sc)
        QLen += 1
        SC += sc

        if  QLen > k:
            SC -= heapq.heappop(Q)
            QLen -= 1

    return SC
            


def f():
    N = int(input())
    LS = []
    RS = []
    SC0 = 0

    for _ in range(N):
        K,L,R = map(int, input().split())
        SC = abs(L - R)
        SC0 += min(L, R)

        if L >= R:
            LS.append((K, SC))
        else:
            RS.append((N-K, SC))

    
    print(SC0 + g(LS) + g(RS))


T = int(input())
for _ in range(T):
    f()

Solution (Python):
from heapq import heappush, heappop
it = lambda: list(map(int, input().strip().split()))


def greedy(A):
    ans = 0
    A.sort(key=lambda x:x[0])
    pq = []
    for k, a, b in A:
        ans += a
        heappush(pq, [a - b, k, a, b])
        while len(pq) > k:
            ans -= heappop(pq)[0]
    return ans


def solve():
    N = int(input())

    prefer_late = []
    prefer_early = []
    for _ in range(N):
        k, a, b = it()
        if a >= b:
            prefer_early.append([k, a, b])
        else:
            prefer_late.append([N - k, b, a])
    
    ans = 0
    ans += greedy(prefer_early)
    ans += greedy(prefer_late)
    print(ans)


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

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

T = int(input())

for _ in range(T):
    N = int(input())
    camel = [tuple(map(int, input().split())) for i in range(N)]

    pos = []
    neg = []

    for i in range(N):
        k, l, r = camel[i]
        if l - r >= 0:
            pos.append((r - l, k, i))
        else:
            neg.append((l - r, N - k, i))

    pos.sort(key=lambda x:x[1], reverse=True)
    p = len(pos)

    heappos = []
    respos = [None for i in range(N)]

    j = 0
    for i in range(N)[::-1]:
        while j < p and pos[j][1] == i + 1:
            heappush(heappos, pos[j])
            j += 1
        if heappos:
            d, k, id = heappop(heappos)
            respos[i] = id
    for i in range(N)[::-1]:
        if respos[i] is None and heappos:
            d, k, id = heappop(heappos)
            respos[i] = id


    neg.sort(key=lambda x:x[1], reverse=True)
    n = len(neg)

    heapneg = []
    resneg = [None for i in range(N)]

    j = 0
    for i in range(N)[::-1]:
        while j < n and neg[j][1] == i + 1:
            heappush(heapneg, neg[j])
            j += 1
        if heapneg:
            d, k, id = heappop(heapneg)
            resneg[i] = id
    while j < n:
        heappush(heapneg, neg[j])
        j += 1
    for i in range(N)[::-1]:
        if resneg[i] is None and heapneg:
            d, k, id = heappop(heapneg)
            resneg[i] = id

    respos = [respos[i] for i in range(N) if respos[i] is not None]
    resneg = [resneg[i] for i in range(N) if resneg[i] is not None]
    res = respos + resneg[::-1]

    ans = 0

    for i in range(N):
        k, l, r = camel[res[i]]
        if k >= i + 1:
            ans += l
        else:
            ans += r

    print(ans)

Solution (Python):
import sys
from heapq import *
def input(): return sys.stdin.readline().strip()


def func(left):
    ll = len(left)
    """
    前から順番に詰めていく方式だと次の反例が存在する：
    ll = 2, left = [(1, 1), (2, 2), (3, 100)]
    (3, 100)をなるべく先頭に置くべきだが、前のコードだと３番目が車で保留。
    ll < 3なのでその時は訪れない。

    なのでやはり後ろから攻めるしかない模様。
    """
    L = [[] for _ in range(ll + 1)]
    for k, v in left:
        if k > ll: k = ll
        L[k].append(v)
    ans = 0
    q = []
    for i in range(ll, 0, -1):
        for v in L[i]: heappush(q, -v)
        if q: ans -= heappop(q)
    return ans


def main():
    T = int(input())
    for _ in range(T):
        n = int(input())
        ans = 0
        left = []
        right = []
        for _ in range(n):
            k, l, r = map(int, input().split())
            if l > r:
                ans += r
                left.append((k, l - r))
            else:
                ans += l
                right.append((n - k, r - l))
        
        
        ans += func(left)
        ans += func(right)
        print(ans)


if __name__ == "__main__":
    main()

Solution (Python):
import heapq
T=int(input())

for _ in range(T):
  N=int(input())
  
  llist=[]
  rlist=[]
  base=0
  for _ in range(N):
    K,L,R=map(int,input().split())    
    if L>R:
      llist.append((K,L-R))
      base+=R
    elif L<R:
      rlist.append((N-K,R-L))
      base+=L
    else:
      base+=L
      
  llist.sort()
  rlist.sort()      
  
  
  
  
  hq_left=[]
  for i,l in llist:
    heapq.heappush(hq_left,l)
    if len(hq_left)>i:
      heapq.heappop(hq_left)
  hq_right=[]
  for i,r in rlist:
    heapq.heappush(hq_right,r)
    if len(hq_right)>i:
      heapq.heappop(hq_right)
      
  answer=base
  while hq_left:
    answer+=heapq.heappop(hq_left)
  while hq_right:
    answer+=heapq.heappop(hq_right)
    
  print(answer)

Solution (Python):
import heapq
T=int(input())

for _ in range(T):
  N=int(input())
  
  llist=[]
  rlist=[]
  base=0
  for _ in range(N):
    K,L,R=map(int,input().split())
    base+=min(L,R)
    if L>R:
      llist.append((K,L-R))
    elif L<R:
      rlist.append((N-K,R-L))
      
  llist.sort()
  rlist.sort()      
  
  
  
  
  hq_left=[]
  for i,l in llist:
    heapq.heappush(hq_left,l)
    if len(hq_left)>i:
      heapq.heappop(hq_left)
  hq_right=[]
  for i,r in rlist:
    heapq.heappush(hq_right,r)
    if len(hq_right)>i:
      heapq.heappop(hq_right)
      
  answer=base
  while hq_left:
    answer+=heapq.heappop(hq_left)
  while hq_right:
    answer+=heapq.heappop(hq_right)
    
  print(answer)

Solution (Python):
from heapq import heappop,heappush
def solve(n,klr):
  kk=[(-1,-1)]
  for k,l,r in klr:kk.append((k-1,r-l))
  kk.sort()
  h=[]
  ans=0
  for i in range(n-1,-1,-1):
    while kk[-1][0]>=i:heappush(h,kk.pop()[1])
    if len(h):ans-=heappop(h)
  return ans

for _ in range(int(input())):
  n=int(input())
  klr=[list(map(int,input().split()))for _ in range(n)]
  pk=[]
  mk=[]
  ans=0
  for i in range(n):
    k,l,r=klr[i]
    ans+=min(l,r)
    if l>=r:pk.append(i)
    else:mk.append(i)
  l=len(pk)
  for i in mk:
    klr[i][0]=n-klr[i][0]
    klr[i][1],klr[i][2]=klr[i][2],klr[i][1]
  ans+=solve(len(pk),[klr[i]for i in pk])+solve(len(mk),[klr[i]for i in mk])
  print(ans)

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

def solve2(left):
    if len(left) == 0:
        return 0
    ans = 0
    k2values = {}
    for v, k in left:
        if k not in k2values:
            k2values[k] = []
        k2values[k].append(v)
    
    pq = []
    maxk = max(k for v,k in left)
    for k in range(maxk, 0, -1):
        if k in k2values:
            for v in k2values[k]:
                heappush(pq, -v)
        if len(pq) > 0:
            v = heappop(pq)
            ans += -v
    return ans


def solve():
    N = int(readline())
    
    left = []
    right = []
    
    ans = 0
    
    for i in range(N):
        k, l, r = map(int, readline().split())
        if l > r:
            left.append((l - r, k))
            ans += r
        else:
            right.append((r - l, N - k))
            ans += l
    
    ans += solve2(left)
    ans += solve2(right)
    
    print(ans)

T = int(readline())
for i in range(T):
    solve()

Solution (Python):
from collections import defaultdict
from heapq import heapify, heappush, heappop
import sys
input = sys.stdin.readline

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

    def f(Ls):
        PQL = []
        for j in range(1, N+1):
            for L in Ls[j]:
                heappush(PQL, L)
            while len(PQL) > j:
                heappop(PQL)
        return sum(PQL)

    ans += f(Ls)
    ans += f(Rs)

    anss.append(ans)

print('\n'.join(map(str, anss)))

Solution (Python):
t=int(input())
import heapq
for _ in range(t):
    n=int(input())
    L=[];R=[]
    ans=0
    for _ in range(n):
        ki,li,ri = map(int, input().split())
        dif=li-ri
        if dif>=0:
            L.append((ki-1,dif))
            ans+=ri
        else:
            R.append((n-ki-1,-dif))
            ans+=li
    L.sort();R.sort()
    hL=[]
    hR=[]
    for i in range(len(L)):
        if L[i][0]>=len(hL):
            heapq.heappush(hL,L[i][1])
        elif L[i][0]==len(hL)-1:
            heapq.heappushpop(hL,L[i][1])
    for i in range(len(R)):
        if R[i][0]>=len(hR):
            heapq.heappush(hR,R[i][1])
        elif R[i][0]==len(hR)-1:
            heapq.heappushpop(hR,R[i][1])
    print(ans+sum(hL)+sum(hR))

Solution (Python):
import sys, io, os, re
from bisect import bisect, bisect_left, bisect_right, insort, insort_left, insort_right
from pprint import pprint
from math import sin, cos, pi, radians, sqrt, floor, ceil
from copy import copy, deepcopy
from collections import deque
from fractions import gcd
from functools import reduce
from itertools import groupby
from heapq import heapify, heappush, heappop



n1 = lambda: int(sys.stdin.readline().strip())
nn = lambda: list(map(int, sys.stdin.readline().strip().split()))
f1 = lambda: float(sys.stdin.readline().strip())
fn = lambda: list(map(float, sys.stdin.readline().strip().split()))
s1 = lambda: sys.stdin.readline().strip()
sn = lambda: list(sys.stdin.readline().strip().split())
nl = lambda n: [n1() for _ in range(n)]
fl = lambda n: [f1() for _ in range(n)]
sl = lambda n: [s1() for _ in range(n)]
nm = lambda n: [nn() for _ in range(n)]
fm = lambda n: [fn() for _ in range(n)]
sm = lambda n: [sn() for _ in range(n)]

def array1(n, d=0): return [d] * n
def array2(n, m, d=0): return [[d] * m for x in range(n)]
def array3(n, m, l, d=0): return [[[d] * l for y in xrange(m)] for x in xrange(n)]
def linc(A, d=1): return map(lambda x: x + d, A)
def ldec(A, d=1): return map(lambda x: x - d, A)


def solve(N, t):
    d1 = array2(N, 0)
    d2 = array2(N, 0)

    t  = [(x[0]-1, x[1], x[2]) for x in t]
    t1 = [(x[0], x[1] - x[2]) for x in t if x[1] >= x[2]]
    t2 = [(N - 2 - x[0], x[2] - x[1]) for x in t if x[1] < x[2] and N - 2 - x[0] >= 0]

    ans = sum([min(x[1], x[2]) for x in t])
    
    for k, dt in t1:
        d1[k].append(dt)

    S = []

    for i in range(N):
        for dt in d1[i]:
            insort(S, dt)

        if len(S) > i:
            S = S[len(S)-i-1:]

    

    ans += sum(S)

    for k, dt in t2:
        d2[k].append(dt)

    S = []
    for i in range(N):
        for dt in d2[i]:
            insort(S, dt)

        if len(S) > i:        
            S = S[len(S)-i-1:]

    
    ans += sum(S)
    print(ans)

T = n1()

for _ in range(T):
    N = n1()
    t = nm(N)
    solve(N, t)

Solution (Python):
import sys
input=sys.stdin.readline
from heapq import heappop,heappush
t=int(input())
for _ in range(t):
	happy=0
	n=int(input())
	camel=[]
	p=[]
	m=[]
	for i in range(n):
		k,l,r=map(int,input().split())
		happy+=min(l,r)
		if l-r>=0:
			p.append((k,l-r))
		else:
			m.append((k,r-l))
	p.sort();m.sort(reverse=True)
	now=0
	P=[];M=[]
	for i in range(n):
		if now<len(p):
			while p[now][0]==i+1:
				heappush(P,(p[now][1],p[now][0]))
				now+=1
				if now==len(p):
					break
		while len(P)>i+1:
			r=heappop(P)
	now=0
	for i in range(n,0,-1):
		if now<len(m):
			while m[now][0]==i:
				heappush(M,(m[now][1],m[now][0]))
				now+=1
				if now==len(m):
					break
		while len(M)>n-i:
			r=heappop(M)
	for x in P:
		happy+=x[0]
	for x in M:
		happy+=x[0]
	print(happy)

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush

sys.setrecursionlimit(10**7)






import math

def solve():
    N = int(sysread())
    KLR_left, KLR_right = [], []
    counts_l, counts_r = [0] * (N+1), [0] * (N+1)

    for _ in range(N):
        k,l,r = map(int, sysread().split())
        if l>r:
            KLR_left.append((k, l, r))
            counts_l[k] += 1
        else:
            KLR_right.append((k, l, r))
            counts_r[k] += 1

    KLR_left = sorted(KLR_left, key = lambda x:x[0], reverse=True)
    KLR_right = sorted(KLR_right, key=lambda x:x[0])
    queue_left = []
    queue_right = []
    dump = []
    SUM = 0
    for i in range(1, N+1):
        for j in range(counts_l[i]):
            k, l, r = KLR_left.pop()
            heappush(queue_left, (l-r, l, r))
            SUM += l

        while True:
            if len(queue_left)>i:
                l_r, l, r = heappop(queue_left)
                dump.append((l_r, l, r))
                SUM -= l_r
            else:break


    
    for i in list(range(1, N+1))[::-1]:
        for j in range(counts_r[i]):
            k, l, r = KLR_right.pop()
            heappush(queue_right, (r-l, l, r))
            SUM += r
        while True:
            if len(queue_right) > N-i:
                try:
                    r_l, l, r = heappop(queue_right)
                except:break
                dump.append((r_l, l, r))
                SUM -= r_l
            else:break
    return SUM

def run():
    T = int(sysread())
    for i in range(T):
        print(solve())



if __name__ == "__main__":
    run()

Solution (Python):

import sys

sysread = sys.stdin.buffer.readline
read = sys.stdin.buffer.read
from heapq import heappop, heappush

sys.setrecursionlimit(10**7)






import math

def solve():
    N = int(sysread())
    KLR_left, KLR_right = [], []
    counts_l, counts_r = [0] * (N+1), [0] * (N+1)

    for _ in range(N):
        k,l,r = map(int, sysread().split())
        if l>r:
            KLR_left.append((k, l, r))
            counts_l[k] += 1
        else:
            KLR_right.append((k, l, r))
            counts_r[k] += 1

    KLR_left = sorted(KLR_left, key = lambda x:x[0], reverse=True)
    KLR_right = sorted(KLR_right, key=lambda x:x[0])
    queue_left = []
    queue_right = []
    dump = []
    SUM = 0
    for i in range(1, N+1):
        for j in range(counts_l[i]):
            k, l, r = KLR_left.pop()
            heappush(queue_left, (l-r, l, r))
            SUM += l

        while True:
            if len(queue_left)>i:
                l_r, l, r = heappop(queue_left)
                dump.append((l_r, l, r))
                SUM -= l_r
            else:break


    
    for i in list(range(1, N+1))[::-1]:
        for j in range(counts_r[i]):
            k, l, r = KLR_right.pop()
            heappush(queue_right, (r-l, l, r))
            SUM += r
        while True:
            if len(queue_right) > N-i:
                try:
                    r_l, l, r = heappop(queue_right)
                except:break
                dump.append((r_l, l, r))
                SUM -= r_l
            else:break
    return SUM

def run():
    T = int(sysread())
    for i in range(T):
        print(solve())



if __name__ == "__main__":
    run()

Solution (Python):
import heapq
T=int(input())
for _ in range(T):
  ans=0
  N=int(input())
  Ls=[[] for _ in range(N)]
  
  Rs=[[] for _ in range(N)]
  for _ in range(N):
    K,L,R=map(int,input().split())
    ans+=max(L,R)
    if L>R:
      Ls[K-1].append(L-R)
    if L<R:
      if K==N:
        ans-=R-L
        continue
      Rs[N-K].append(R-L)
  
  dat=[]
  heapq.heapify(dat)
  for i in range(N):
    if not Ls[i]:
      continue
    for l in Ls[i]:
      heapq.heappush(dat,l)
    while len(dat)>i+1:
      ans-=heapq.heappop(dat)
  
  dat=[]
  heapq.heapify(dat)
  for i in range(1,N):
    if not Rs[i]:
      continue
    for l in Rs[i]:
      heapq.heappush(dat,l)
    while len(dat)>i:
      ans-=heapq.heappop(dat)
  print(ans)

Solution (Python):
import sys
from heapq import heappop, heappush
def main():
    def input(): return sys.stdin.readline().rstrip()
    n = int(input())
    l_camel = [[] for _ in range(n)]
    r_camel = [[] for _ in range(n)]
    ans = 0
    for _ in range(n):
        k, l, r = map(int, input().split())
        if l >= r:
            ans += r
            l_camel[k-1].append(l-r)
        else:
            ans += l
            r_camel[~(k-1)].append(r-l)
    
    cur = 0
    que = []
    for i in range(n):
        for el in l_camel[i]:
            heappush(que, el)
        while len(que) > i+1:
            heappop(que)
    ans += sum(que)

    que = []
    for i in range(n):
        for el in r_camel[i]:
            heappush(que, el)
        while len(que) > i:
            heappop(que)
    ans += sum(que)
    print(ans)


if __name__ == '__main__':
    t = int(input())
    for _ in range(t):
        main()

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

def f(p):
  res = 0
  s = len(p)
  for i in range(s):
    if p[i][0] > s:
      p[i][0] = s
  p.sort(reverse = True)
  hq = []
  idx = 0
  for i in range(s,0,-1):
    
    while(idx < s and p[idx][0] == i):
      heappush(hq,-p[idx][1])
      idx += 1
    
    if len(hq) > 0:
      res -= heappop(hq)
      
  return res

def solve():
  n = int(input())
  pl = []
  pr = []
  ans = 0
  for i in range(n):
    k,l,r = map(int,input().split())
    m = min(l,r)
    l -= m
    r -= m
    ans += m
    if l > 0:
      pl.append([k,l])
    else:
      pr.append([n-k,r])
  
  ans += f(pl)
  ans += f(pr)
  print(ans)

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