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
t = int(input())
for _ in range(t):
    n = int(input())
    lefts = [[] for _ in range(n)]
    rights = [[] for _ in range(n)]
    ans = 0
    for i in range(n):
        k, l, r = map(int, input().split())
        k -= 1
        if l >= r:
            ans += r
            lefts[k].append(l-r)
        else:
            ans += l
            rights[k].append(r-l)
    l_queue = []
    heapq.heapify(l_queue)
    for i in range(n):
        for j in range(len(lefts[i])):
            ans += lefts[i][j]
            heapq.heappush(l_queue,lefts[i][j])
        while len(l_queue) > i+1:
            m = heapq.heappop(l_queue)
            ans -= m
    r_queue = []
    heapq.heapify(r_queue)
    for i in range(n):
        for j in range(len(rights[n-i-1])):
            ans += rights[n-i-1][j]
            heapq.heappush(r_queue, rights[n-i-1][j])
        while len(r_queue) > i:
            m = heapq.heappop(r_queue)
            ans -= m
    print(ans)

Solution (Python):
import heapq
T=int(input())
for _ in range(T):
    N=int(input())
    lq=[[] for _ in range(N+1)]
    rq=[[] for _ in range(N+1)]
    ans=0
    for _ in range(N):
        K,L,R=map(int,input().split())
        ans+=min(L,R)
        if L>R:
            lq[K].append(L-R)
        else:
            rq[K].append(R-L)
    ls=[]
    for i in range(1,N+1):
        for v in lq[i]:
            heapq.heappush(ls,v)
        while len(ls)>i:
            heapq.heappop(ls)
    ans+=sum(ls)
    rs=[]
    for i in range(N,0,-1):
        for v in rq[i]:
            heapq.heappush(rs,v)
        while len(rs)>N-i:
            heapq.heappop(rs)
    ans+=sum(rs)
    print(ans)

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)
  Mdata = []
  Udata = []
  for K,L,R in data:
    if L>=R:
      Mdata.append([K,L,R])
    else:
      Udata.append([K,L,R])
  Mdata.sort(key=lambda x:-abs(x[1]-x[2]))
  Udata.sort(key=lambda x:-abs(x[1]-x[2]))
  ans = 0
  Mlen = len(Mdata)
  Ulen = len(Udata)
  MAE = [i for i in range(Mlen)]
  def CANSIT_MAE(x):
    if MAE[x] == -1:
      return -1
    elif MAE[x] == x:
      MAE[x] = x-1
      return x
    else:
      MAE[x] = CANSIT_MAE(MAE[x])
      return MAE[x]
  USHIRO = [i for i in range(Ulen)]
  def CANSIT_USHIRO(x):
    if x == -1:
      return -1
    elif USHIRO[x] == -1:
      return -1
    elif USHIRO[x] == x:
      USHIRO[x] = x-1
      return x
    else:
      USHIRO[x] = CANSIT_USHIRO(USHIRO[x])
      return USHIRO[x]
  for K,L,R in Mdata:
    if CANSIT_MAE(min(K-1,Mlen-1))!=-1:
      ans += L
    else:
      ans += R
  for K,L,R in Udata:
    if CANSIT_USHIRO(min(N-1-K,Ulen-1))!=-1:
      ans += R
    else:
      ans += L
  print(ans)

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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

for _ in range(INT()):
    N = INT()
    ans = 0
    adjli1 = [[] for i in range(N)]
    adjli2 = [[] for i in range(N+1)]
    for _ in range(N):
        k, l, r = MAP()
        k -= 1
        if l > r:
            adjli1[k].append(l - r)
        elif l < r:
            adjli2[k+1].append(r - l)
        ans += min(l, r)

    que = []
    for i in range(N):
        for a in adjli1[i]:
            heappush(que, a)
        while len(que) > i+1:
            heappop(que)
    ans += sum(que)
    que = []
    for i in range(N-1, -1, -1):
        for a in adjli2[i]:
            heappush(que, a)
        while len(que) > N-i:
            heappop(que)
    ans += sum(que)
    print(ans)

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

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7
EPS = 10 ** -10

for _ in range(INT()):
    N = INT()
    ans = 0
    adjli1 = [[] for i in range(N)]
    adjli2 = [[] for i in range(N+1)]
    for _ in range(N):
        k, l, r = MAP()
        k -= 1
        if l > r:
            adjli1[k].append(l - r)
        elif l < r:
            adjli2[k+1].append(r - l)
        ans += min(l, r)

    que = []
    for i in range(N):
        for a in adjli1[i]:
            heappush(que, a)
        while len(que) > i+1:
            heappop(que)
    ans += sum(que)
    que = []
    for i in range(N-1, -1, -1):
        for a in adjli2[i]:
            heappush(que, a)
        while len(que) > N-i:
            heappop(que)
    ans += sum(que)
    print(ans)

Solution (Python):
from heapq import heappop, heappush

def calc(KD, N):
  now = 0
  hq = []
  for i in range(1, N+1):
    while now < N and KD[now][0] <= i:
      heappush(hq, KD[now][1])
      now += 1
    while len(hq) > i:
      heappop(hq)
  res = sum(hq)
  while now < N:
    res += KD[now][1]
    now += 1
  return res

def solve(KLR, N):
  res = 0
  KD_l = []; KD_r = []
  for k, l, r in KLR:
    if l < r:
      if k < N:
        KD_r.append((N-k, r-l))
      res += l
    elif l > r:
      if k < N:
        KD_l.append((k, l-r))
        res += r
      else:
        res += l
    else:
      res += l
  KD_l.sort(); KD_r.sort()
  Nl = len(KD_l); Nr = len(KD_r)
  res += calc(KD_l, Nl)
  res += calc(KD_r, Nr)
  return res


ans = []
T = int(input())
for i in range(T):
  N = int(input())
  KLR = [tuple(map(int, input().split())) for i in range(N)]
  ans.append(solve(KLR, N))

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

Solution (Python):
import sys
input = sys.stdin.readline
import heapq
T = int(input())
for _ in range(T):
    N = int(input())
    KLR = [tuple(map(int,input().split())) for i in range(N)]
    ans = 0
    LK = [[] for _ in range(N+1)]
    RK = [[] for _ in range(N+1)]
    for k,l,r in KLR:
        ans += min(l,r)
        if l >= r:
            LK[k].append(l-r)
        else:
            RK[k].append(r-l)
    lq = []
    for i in range(1,N+1):
        for v in LK[i]:
            heapq.heappush(lq, v)
        while len(lq) > i:
            heapq.heappop(lq)
    ans += sum(lq)
    rq = []
    for i in range(N,0,-1):
        for v in RK[i]:
            heapq.heappush(rq, v)
        while len(rq) >= N+1-i:
            heapq.heappop(rq)
    ans += sum(rq)
    print(ans)

Solution (Python):
ma = lambda :map(int,input().split())
ni = lambda:int(input())
import collections
import math
import itertools
import heapq as hq
gcd = math.gcd
t = ni()

def f1(a2):
    a2.sort(key=lambda x:x[1])
    l = len(a2)
    que = []
    ret = 0
    for dif,k in a2:
        if len(que) < k: 
            ret +=dif
            hq.heappush(que,dif)
        else:
            if que[0] < dif:
                ret += dif - que[0]
                hq.heappushpop(que,dif)
    return ret
def f2(a2,n):
    a2.sort(key=lambda x:x[1],reverse=True)
    l = len(a2)
    que = []
    ret = 0
    for dif,k in a2:
        if len(que) + k < n: 
            ret +=dif
            hq.heappush(que,dif)
        else:
            if que and que[0] < dif:
                ret += dif - que[0]
                hq.heappushpop(que,dif)
    return ret

def solve(n):
    dp = [] 
    dm = [] 
    ans = 0
    for i in range(n):
        k,l,r = ma()
        if r-l >0:
            dp.append((r-l,k))
        else:
            dm.append((l-r,k))
        ans +=min(r,l) 

    
    ans += f2(dp,n) + f1(dm)

    return ans
for i in range(t):
    n = ni()
    print(solve(n))

Solution (Python):
import heapq
t = int(input())
while t:
    t-=1
    n = int(input())
    klr = [list(map(int, input().split())) for i in range(n)]
    klr.sort()
    q = []
    ans = 0
    for i in range(n):
        K = klr[i][0]
        L = klr[i][1]
        R = klr[i][2]
        if L >= R:
            ans += L
            heapq.heappush(q,L-R)
            while len(q) > K:
                dec = heapq.heappop(q)
                ans -= dec
    q = []
    for i in reversed(range(n)):
        K = klr[i][0]
        L = klr[i][1]
        R = klr[i][2]
        if L < R:
            ans += R
            heapq.heappush(q,R-L)
            while len(q) > n-K:
                dec = heapq.heappop(q)
                ans -= dec    
    print(ans)

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

for _ in range(T):
    n = int(input())
    ans = 0
    
    lamount,ramount = 0,0
    k,l,r = [0]*n,[0]*n,[0]*n
    
    ll,rr = [],[]
    for i in range(n):
        k[i],l[i],r[i] = map(int,input().split())
        if l[i] >= r[i]:
            lamount += 1
            ans += r[i]
            ll.append(i)
        else:
            ramount += 1
            ans += l[i]
            rr.append(i)
            
    ldek = [[] for _ in range(lamount)]
    rdek = [[] for _ in range(ramount)]
    
    for i in ll:
        ldek[min(lamount-1,k[i]-1)].append(l[i]-r[i])
    
    for i in rr:
        if n != k[i]:
            rdek[min(ramount-1,n-1-k[i])].append(r[i]-l[i])
        
    cur = []
    heapq.heapify(cur)
    
    for l in range(lamount-1,-1,-1):
        for k in ldek[l]:
            heapq.heappush(cur, k*(-1))
            
        if cur != []:
            mi = heapq.heappop(cur)
            ans += mi * (-1)
            
    cur = []
    heapq.heapify(cur)
    
    for l in range(ramount-1,-1,-1):
        for k in rdek[l]:
            heapq.heappush(cur, k*(-1))
            
        if cur != []:
            mi = heapq.heappop(cur)
            ans += mi * (-1)
            
    print(ans)

Solution (Python):
import heapq
T = int(input())
for _ in range(T):
    N = int(input())
    KLR = [list(map(int, input().split())) for i in range(N)]
    ans = 0
    for i in range(N):
        ans += min(KLR[i][1], KLR[i][2])
    KX = [(K, L-R) for K, L, R in KLR if L-R >= 0]
    KX.sort()
    hq = []
    id = 0
    for i in range(1, N+1):
        while(id < len(KX) and KX[id][0] == i):
            heapq.heappush(hq, KX[id][1])
            id += 1
        while(len(hq) > i):
            heapq.heappop(hq)
        
    ans += sum(hq)
    L = len(KX)
    KX = [(N-K, R-L) for K, L, R in KLR if R-L > 0]
    KX.sort()
    hq = []

    id = 0
    for i in range(N):
        while(id < len(KX) and KX[id][0] == i):
            heapq.heappush(hq, KX[id][1])
            id += 1
        while(len(hq) > i):
            heapq.heappop(hq)
        

    ans += sum(hq)

    print(ans)

Solution (Python):
import heapq  
def priority(klr):
    return abs(klr[1]-klr[2])
              
def process(KP):
    q = []    
    for kp in KP:
        if kp[0] < len(q) and len(q) > 0 and q[0] < kp[1]:
            heapq.heappop(q)
        if kp[0] >= len(q):
            heapq.heappush(q, kp[1])
    return sum(q)
              
def solve():  
    N = int(input())
    KLR = []  
    for _ in range(N):
        klr = list(map(int, input().split()))
        klr[0] -= 1 
        KLR.append(klr)
    ans = 0   
    L = []    
    R = []    
    for klr in KLR:
        if klr[1] > klr[2]:
            ans += klr[2]
            L.append((klr[0], klr[1]-klr[2]))
        elif klr[1] < klr[2]:
            ans += klr[1]
            R.append((N-1-klr[0]-1, klr[2]-klr[1]))
        else: 
            ans += klr[1]
    L.sort(key=lambda kp: kp[0])
    R.sort(key=lambda kp: kp[0])
    ans += process(L)
    ans += process(R)
    print(ans)
              
T = int(input())
              
for _ in range(T):
    solve()

Solution (Python):
import heapq
T=int(input())
for case in range(T):
    N=int(input())
    KLR=[[],[]]
    ans=0
    for i in range(N):
        k,l,r=map(int,input().split())
        ans+=min(l,r)
        if l>=r:
            KLR[0].append((k,l,r))
        else:
            KLR[1].append((N-k,r,l))
    Len=[len(KLR[0]),len(KLR[1])]
    for i in range(2):
        KLR[i].sort()
        for j in range(Len[i]):
            k,l,r=KLR[i][j]
            KLR[i][j]=(min(k,Len[i]),l,r)
        q=[]
        index=0
        for j in range(Len[i]+1):
            while(index<Len[i]):
                k,l,r=KLR[i][index]
                if k==j:
                    heapq.heappush(q,(l-r,k,l,r))
                    index+=1
                else:
                    break
            while(len(q)>j):
                heapq.heappop(q)
        while(len(q)>0):
            ans+=heapq.heappop(q)[0]
    print(ans)

Solution (Python):
import sys,heapq

input=sys.stdin.readline

for _ in range(int(input())):
    N=int(input())
    camelL=[]
    camelR=[]
    ans=0
    for i in range(N):
        k,l,r=map(int,input().split())
        if l<r:
            camelR.append((N-k,r-l))
            ans+=l
        elif l>r:
            camelL.append((k,l-r))
            ans+=r
        else:
            ans+=l
    camelL.sort()
    que=[]
    for i in range(len(camelL),0,-1):
        while camelL and camelL[-1][0]>=i:
            id,val=camelL.pop()
            heapq.heappush(que,(-val,id))
        if que:
            val,id=heapq.heappop(que)
            ans-=val
    camelR.sort()
    que=[]
    for i in range(len(camelR),0,-1):
        while camelR and camelR[-1][0]>=i:
            id,val=camelR.pop()
            heapq.heappush(que,(-val,id))
        if que:
            val,id=heapq.heappop(que)
            ans-=val
    print(ans)

Solution (Python):
import sys
import math
from collections import deque
import heapq as hq

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    T = NI()
    for _ in range(T):
        N = NI()
        camels = [NLI() for _ in range(N)]
        base = 0
        camels_L = [[] for _ in range(N+1)]
        camels_R = [[] for _ in range(N+1)]
        
        for camel in camels:
            if camel[1] >= camel[2]:
                camels_L[camel[0]].append(camel[1] - camel[2])
                base += camel[2] 
            else:
                camels_R[N - camel[0]].append(camel[2] - camel[1])
                base += camel[1] 
        ans = 0
        heap_camels = []
        hq.heapify(heap_camels)
        for i in range(1, N+1):
            for camel in camels_L[i]:
                hq.heappush(heap_camels, camel)
            while len(heap_camels) > i:
                hq.heappop(heap_camels)
        ans += sum(heap_camels)

        heap_camels = []
        hq.heapify(heap_camels)
        for i in range(1, N+1):
            for camel in camels_R[i]:
                hq.heappush(heap_camels, camel)
            while len(heap_camels) > i:
                hq.heappop(heap_camels)
        ans += sum(heap_camels)
        print(ans + base)



if __name__ == "__main__":
    main()

Solution (Python):
import sys
import math
from collections import deque
import heapq as hq

sys.setrecursionlimit(1000000)
MOD = 10 ** 9 + 7
input = lambda: sys.stdin.readline().strip()
NI = lambda: int(input())
NMI = lambda: map(int, input().split())
NLI = lambda: list(NMI())
SI = lambda: input()


def make_grid(h, w, num): return [[int(num)] * w for _ in range(h)]


def main():
    T = NI()
    for _ in range(T):
        N = NI()
        camels = [NLI() for _ in range(N)]
        base = 0
        camels_L = [[] for _ in range(N+1)]
        camels_R = [[] for _ in range(N+1)]
        
        for camel in camels:
            if camel[1] >= camel[2]:
                camels_L[camel[0]].append(camel[1] - camel[2])
                base += camel[2] 
            else:
                camels_R[N - camel[0]].append(camel[2] - camel[1])
                base += camel[1] 
        ans = 0
        heap_camels = []
        hq.heapify(heap_camels)
        for i in range(1, N+1):
            for camel in camels_L[i]:
                hq.heappush(heap_camels, camel)
            while len(heap_camels) > i:
                hq.heappop(heap_camels)
        if heap_camels:
            ans += sum(heap_camels)

        heap_camels = []
        hq.heapify(heap_camels)
        for i in range(1, N+1):
            for camel in camels_R[i]:
                hq.heappush(heap_camels, camel)
            while len(heap_camels) > i:
                hq.heappop(heap_camels)
        if heap_camels:
            ans += sum(heap_camels)
        print(ans + base)



if __name__ == "__main__":
    main()

Solution (Python):

import sys
from heapq import heappush,heappop,heapify
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

T=int(input())
for _ in range(T):
    N=int(input())
    ans=0
    left=[]
    right=[]
    for i in range(N):
        K,L,R=map(int,input().split())
        ans+=min(L,R)
        if L>=R:
            left.append((K,L-R))
        else:
            right.append((N-K,R-L))
    left.sort(key=lambda t:t[0])
    right.sort(key=lambda t:t[0])
    for l in [left,right]:
        h=[]
        for k,p in l:
            if len(h)<k:
                heappush(h,p)
            else:
                if h:
                    heappush(h,max(heappop(h),p))
        ans+=sum(h)
    print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

t = I()
for _ in range(t):
    n = I()
    klr = [LI() for _ in range(n)]
    ans = 0
    L = []
    R = []
    for k,l,r in klr:
        if l >= r:
            L.append([k, l-r])
        else:
            R.append([n-k, r-l])
        ans += min(l, r)
    L.sort()
    R.sort()
    hl = []
    hr = []
    cnt = 0
    for k, x in L:
        heappush(hl, x)
        cnt += 1
        if cnt > k:
            heappop(hl)
            cnt -= 1
    cnt = 0
    for k, x in R:
        heappush(hr, x)
        cnt += 1
        if cnt > k:
            heappop(hr)
            cnt -= 1
    ans += sum(hl) + sum(hr)
    print(ans)

Solution (Python):


import sys
import math
from bisect import bisect_right as br
from bisect import bisect_left as bl
sys.setrecursionlimit(2147483647)
from heapq import heappush, heappop,heappushpop
from collections import defaultdict
from itertools import accumulate
from collections import Counter
from collections import deque
from operator import itemgetter
from itertools import permutations
mod = 10**9 + 7
inf = float('inf')
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))

t = I()
for _ in range(t):
    n = I()
    klr = [LI() for _ in range(n)]
    ans = 0
    L = []
    R = []
    for k,l,r in klr:
        if l >= r:
            L.append([k, l-r])
        else:
            R.append([n-k, r-l])
        ans += min(l, r)
    L.sort()
    R.sort()
    hl = []
    hr = []
    for k, x in L:
        heappush(hl, x)
        if len(hl) > k:
            heappop(hl)
    for k, x in R:
        heappush(hr, x)
        if len(hr) > k:
            heappop(hr)
    ans += sum(hl) + sum(hr)
    print(ans)

Solution (Python):
import sys 
from heapq import heapify,heappop,heappush,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 i in range(N):
        k = K[i]; l = L[i]; r = R[i]
        k -= 1
        if l >= r:
            left[k].append(l-r)
            score += r
        else:
            right[k].append(r-l)
            score += l
    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)
    print(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)
    main(N,K,L,R)

Solution (Python):
import heapq

T = int(input())

for _ in range(T):
    N = int(input())
    List = []
    ans = 0
    
    for _ in range(N):
        K, L, R = map(int,input().split())
        ans += min(L, R)
        List.append((K, L, R))
    
    S1 = []
    S2 = []
    
    List.sort()
    
    for i in range(N):
        K, L, R = List[i]
        if L-R > 0:
            heapq.heappush(S1, L-R)
        if K < len(S1):
            heapq.heappop(S1)
    
    for i in range(N):
        K, L, R = List[N-i-1]
        K = N - K
        
        if R-L > 0:
            heapq.heappush(S2, R-L)
        if K < len(S2):
            heapq.heappop(S2)
    
    ans += sum(S1) + sum(S2)
    
    print(ans)

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):
T = int(input())
import heapq
ans = []
for _ in range(T):
    n = int(input())
    ans = 0
    q1,q2,l1,l2 = [],[],[],[]
    for _ in range(n):
        k,l,r = map(int,input().split())
        if l>r:
            l1 += [(k,l-r)]
        else:
            l2 += [(n-k,r-l)]
        ans += min(l,r)
    l1.sort()
    l2.sort()
    
    for k,d in l1:
        heapq.heappush(q1, d)
        if len(q1)>k: heapq.heappop(q1)
    for k,d in l2:
        heapq.heappush(q2,d)
        if len(q2)>k: heapq.heappop(q2)
    ans += sum(q1) + sum(q2)
    print(ans)

Solution (Python):
import heapq
for _ in range(int(input())):
  N=int(input())
  ls=[[int(s) for s in input().split()] for _ in range(N)]
  
  lsL=[]
  lsR=[]
  constL=0
  constR=0
  for i in range(N):
    if ls[i][1]>=ls[i][2]:
      lsL.append((ls[i][0],ls[i][1]-ls[i][2]))
      constL+=ls[i][2]
    else:
      lsR.append((N-ls[i][0],ls[i][2]-ls[i][1]))
      constR+=ls[i][1]
  lsL=sorted(lsL, key=lambda x:-x[0])
  lsR=sorted(lsR, key=lambda x:-x[0])
  
  trainL=[]
  trainR=[]
  heapq.heapify(trainL)
  heapq.heapify(trainR)
  len_trainL=0
  len_trainR=0
  
  for j in range(1,N+1):
    
    while lsL!=[] and lsL[-1][0]==j:
      len_trainL+=1
      heapq.heappush(trainL,lsL[-1][1])
      del lsL[-1]
    
    while len_trainL>j:
      a=heapq.heappop(trainL)
      len_trainL-=1
      
  for j in range(N+1):
    
    while lsR!=[] and lsR[-1][0]==j:
      len_trainR+=1
      heapq.heappush(trainR,lsR[-1][1])
      del lsR[-1]
    
    while len_trainR>j:
      a=heapq.heappop(trainR)
      len_trainR-=1
      
  print(constL+constR+sum(trainL)+sum(trainR))

Solution (Python):
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor, cos, radians, pi, sin
from operator import mul
from functools import reduce
from operator import mul


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 10 ** 9 + 7

t = I()
for _ in range(t):
    n = I()
    ans = 0
    q1 = []
    q2 = []
    L1 = []
    L2 = []
    for _ in range(n):
        k, l, r = LI()
        if l > r:
            L1 += [(k, l - r)]
        else:
            L2 += [(n - k, r - l)]
        ans += min(l, r)
    L1.sort()
    L2.sort()
    for ki, d in L1:
        heappush(q1, d)
        if len(q1) > ki:
            heappop(q1)
    for ki, d in L2:
        heappush(q2, d)
        if len(q2) > ki:
            heappop(q2)
    ans += sum(q1) + sum(q2)
    print(ans)

Solution (Python):
from heapq import heappop, heappush
import sys
input = sys.stdin.readline
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)