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 heappush, heappop
T = int(input())

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

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))
    print(process(arr1) + process(arr2))

Solution (Python):
from heapq import *
import sys

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

class SegtreeMax():
    def __init__(self, aa):
        n=len(aa)
        self.inf = 10 ** 16
        tree_width = 2
        while tree_width < n:
            tree_width *= 2
        self.tree_width = tree_width
        self.tree = [0] * (tree_width * 2 - 1)
        self.tree[self.tree_width-1:self.tree_width-1+len(aa)]=aa
        for i in range(tree_width-2,-1,-1):
            self.tree[i]=max(self.tree[i*2+1],self.tree[i*2+2])

    def update(self, i, a):
        seg_i = self.tree_width - 1 + i
        self.tree[seg_i] = a
        while seg_i != 0:
            seg_i = (seg_i - 1) // 2
            self.tree[seg_i] = max(self.tree[seg_i * 2 + 1], self.tree[seg_i * 2 + 2])

    def element(self, i):
        return self.tree[self.tree_width - 1 + i]

    
    def max(self, l, r, seg_i=0, segL=0, segR=-1):
        if segR == -1: segR = self.tree_width
        if r <= segL or segR <= l: return 0
        if l <= segL and segR <= r: return self.tree[seg_i]
        segM = (segL + segR) // 2
        ret0 = self.max(l, r, seg_i * 2 + 1, segL, segM)
        ret1 = self.max(l, r, seg_i * 2 + 2, segM, segR)
        return max(ret0, ret1)

for _ in range(II()):
    n=II()
    hp=[]
    hpr=[]
    ans=0
    for _ in range(n):
        k,l,r=MI()
        if r<l:heappush(hp,(r-l,l,r,k))
        elif r>l:heappush(hpr,(-r+l,l,r,k))
        else:ans+=r

    st=SegtreeMax(list(range(n+5)))
    for i in range(n+1):st.update(i,i)
    while hp:
        d,l,r,k=heappop(hp)
        i=st.max(0,k+1)
        if i:
            ans+=l
            st.update(i,0)
        else:
            ans+=r

    st=SegtreeMax(list(range(n+5)))
    for i in range(n+1):st.update(i,i)
    while hpr:
        d,l,r,k=heappop(hpr)
        k=n-k
        i=st.max(0,k+1)
        if i:
            ans+=r
            st.update(i,0)
        else:
            ans+=l

    print(ans)

Solution (Python):
from heapq import heappush, heappushpop

T = int(input())
ans = []
for _ in range(T):
    N = int(input())
    first = []
    last = []
    base = 0
    base_max = 0
    for _ in range(N):
        k, l, r = map(int, input().split())
        if k == N:
            r = l
        if l > r:
            first.append([k, l - r])
        elif r > l:
            last.append([N - k, r - l])
        base += min(l, r)
        base_max += max(l, r)
    first.sort()
    last.sort()

    pool = []
    for k, p in first:
        if len(pool) < k:
            heappush(pool, p)
        else:
            if pool and pool[0] < p:
                heappushpop(pool, p)
    base += sum(pool)
    pool = []
    for k, p in last:
        if len(pool) < k:
            heappush(pool, p)
        else:
            if pool and pool[0] < p:
                heappushpop(pool, p)
    base += sum(pool)
    ans.append(base)
    pass
print(*ans, sep="\n")

Solution (Python):
import sys; input = sys.stdin.buffer.readline
sys.setrecursionlimit(10**7)
from collections import defaultdict
con = 10 ** 9 + 7; INF = float("inf")
def getlist():
	return list(map(int, input().split()))

class SegmentTree(object):
	
	def __init__(self, N):
		self.N0 = 2 ** (N - 1).bit_length()
		self.data = [INF] * (2 * self.N0)

	
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = min(self.data[2 * k + 1], self.data[2 * k + 2])

	
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = INF
		while L < R:
			if R & 1:
				R -= 1
				m = min(m, self.data[R - 1])
			if L & 1:
				m = min(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m

class SegmentTreeMAX(object):
	
	def __init__(self, N):
		self.N0 = 2 ** (N - 1).bit_length()
		self.data = [-INF] * (2 * self.N0)

	
	def update(self, k, x):
		k += self.N0 - 1
		self.data[k] = x
		while k > 0:
			k = (k - 1) // 2
			self.data[k] = max(self.data[2 * k + 1], self.data[2 * k + 2])

	
	def query(self, l, r):
		L = l + self.N0; R = r + self.N0 + 1
		m = -INF
		while L < R:
			if R & 1:
				R -= 1
				m = max(m, self.data[R - 1])
			if L & 1:
				m = max(m, self.data[L - 1])
				L += 1
			L >>= 1; R >>= 1

		return m



def main():
	T = int(input())
	for _ in range(T):
		N = int(input())
		Seg = SegmentTree(N)
		SegMAX = SegmentTreeMAX(N)
		
		for i in range(N):
			Seg.update(i, i)
			SegMAX.update(i, i)

		ans = 0
		Lis = []
		for i in range(N):
			K, L, R = getlist()
			ans += R
			dif = L - R
			Lis.append([abs(dif), dif, K - 1])

		Lis.sort()
		for i in range(N):
			ab, diff, ind = Lis[-1 - i]
			
			if diff >= 0:
				if ind >= N - 1:
					ans += diff
				else:
					segInd = SegMAX.query(0, ind)
					if segInd == -INF:
						pass
					else:
						ans += diff
						SegMAX.update(segInd, -INF)
			else:
				if ind >= N - 1:
					ans += diff
				
				else:
					segInd = Seg.query(ind + 1, N - 1)
					if segInd == INF:
						ans += diff
					else:
						Seg.update(segInd, INF)

		print(ans)


if __name__ == '__main__':
	main()

Solution (Python):

import sys
input = sys.stdin.readline
import heapq

class BinaryIndexedTree:
    
    def __init__(self, array):
        self.len = len(array)
        self.data = [0] + array
        self.build()

    def build(self):
        for i in range(1, self.len):
            if i + (i & -i) > self.len:
                continue
            self.data[i + (i & -i)] += self.data[i]

    
    def add(self, x, w):
        x += 1
        while x <= self.len:
            self.data[x] += w
            x += x & -x

    
    def sum(self, x):
        ret = 0
        while x > 0:
            ret += self.data[x]
            x -= x & -x
        return ret

    
    def bisect_left(self, w):
        if w <= 0:
            return 0
        x = 0
        delta = pow(2, (self.len - 1).bit_length())
        while delta > 0:
            if x + delta <= self.len and self.data[x + delta] < w:
                w -= self.data[x + delta]
                x += delta
            delta >>= 1
        return x

t = int(input())
for _ in range(t):
    n = int(input())
    q = []
    base = 0
    left = BinaryIndexedTree([0] * n)
    right = BinaryIndexedTree([0] * n)
    left_bag = [[] for _ in range(n)]
    right_bag = [[] for _ in range(n)]
    for _ in range(n):
        k, l, r = map(int, input().split())
        if k == n:
            base += l
            continue
        if l == r:
            base += l
        elif l > r:
            q.append((l-r, 0, k-1))
            base += r
            left_bag[k-1].append(l-r)
        else:
            q.append((r-l, 1, n-k-1))
            base += l
            right_bag[n-k-1].append(r-l)
    
    left_bag.reverse()
    hq = []
    for bag in left_bag:
        if bag:
            for item in bag:
                heapq.heappush(hq, -item)
        if hq:
            base += -heapq.heappop(hq) 
    right_bag.reverse()
    hq = []
    for bag in right_bag:
        if bag:
            for item in bag:
                heapq.heappush(hq, -item)
        if hq:
            base += -heapq.heappop(hq) 
    print(base)

Solution (Python):
import heapq as hq

T = int(input())
for _ in range(T):
    N = int(input())
    Cp = []
    Cn = []
    ans = 0
    for _ in range(N):
        K, L, R = map(int, input().split())
        D = L-R
        if D>=0:
            ans += R
            Cp.append((K,D))
        else:
            ans += L
            Cn.append((N-K,-D))

    Cp = sorted(Cp, reverse=True)
    Cn = sorted(Cn, reverse=True)
    Np = len(Cp)
    Nn = len(Cn)

    i = 0
    h = []
    for n in range(Np, 0, -1):
        while i<Np:
            k, d = Cp[i]
            if k<n: break
            hq.heappush(h, -d)
            i+=1

        if len(h): ans += -hq.heappop(h)

    i = 0
    h = []
    for n in range(Nn, 0, -1):
        while i<Nn:
            k, d = Cn[i]
            if k<n: break
            hq.heappush(h, -d)
            i+=1

        if len(h): ans += -hq.heappop(h)

    print(ans)

Solution (Python):
import heapq

def func():
    N = int(input())
    L_list = []
    L_ind = [[]for i in range(N)]
    R_list = []
    R_ind = [[]for i in range(N+1)]
    ans = 0
    for i in range(N):
        k,l,r = map(int,input().split())
        if l > r:
            L_list.append(l-r)
            L_ind[k-1].append(len(L_list)-1)
            ans += r
        elif r > l:
            R_list.append(r-l)
            R_ind[N-k].append(len(R_list)-1)
            ans += l
        else:
            ans += l

    L_heap = []
    for i in range(N):
        for j in L_ind[i]:
            heapq.heappush(L_heap,L_list[j])
        while len(L_heap) > i+1:
            heapq.heappop(L_heap)
    R_heap = []
    for i in range(N):
        for j in R_ind[i+1]:
            heapq.heappush(R_heap,R_list[j])
        while len(R_heap) > i+1:
            heapq.heappop(R_heap)
    return(ans+sum(L_heap)+sum(R_heap))
    

T= int(input())
for i in range(T):
    print(func())

Solution (Python):
import sys
input=lambda: sys.stdin.readline().rstrip()
t=int(input())
import heapq
for _ in range(t):
  n=int(input())
  ans=0
  C=[]
  D=[]
  for i in range(n):
    k,l,r=map(int,input().split())
    if l>r:
      C.append((k,l-r))
      ans+=r
    else:
      D.append((n-k,r-l))
      ans+=l
  C.sort(key=lambda x:(x[0],x[1]), reverse=True)
  D.sort(key=lambda x:(x[0],x[1]), reverse=True)
  c,d=len(C),len(D)
  H=[]
  cur=0
  for i in range(1,c+1)[::-1]:
    while cur<c:
      k,l=C[cur]
      if k<i:
        break
      else:
        heapq.heappush(H,(-l,k))
        cur+=1
    if H:
      ll,kk=heapq.heappop(H)
      ll=-ll
      ans+=ll
  H=[]
  cur=0
  for i in range(1,d+1)[::-1]:
    while cur<d:
      k,l=D[cur]
      if k<i:
        break
      else:
        heapq.heappush(H,(-l,k))
        cur+=1
    if H:
      ll,kk=heapq.heappop(H)
      ll=-ll
      ans+=ll
  print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**7)

readline = sys.stdin.buffer.readline
def readstr():return readline().rstrip().decode()
def readstrs():return list(readline().decode().split())
def readint():return int(readline())
def readints():return list(map(int,readline().split()))
def printrows(x):print('\n'.join(map(str,x)))
def printline(x):print(' '.join(map(str,x)))
import heapq


t = readint()
ans = []

for _ in range(t):
    n = readint()
    a = []
    b = []
    score = 0
    for i in range(n):
        k,l,r = readints()
        if k==n:
            score += l
        elif l>r:
            a.append([k,l,r])
            score += l
        elif l<r:
            b.append([n-k,l,r])
            score += r
        else:
            score += r
    a.sort()
    b.sort()
    left = []
    right = []
    heapq.heapify(left)
    heapq.heapify(right)
    lenl = 0
    lenr = 0
    for k,l,r in a:
        if k>lenl:
            heapq.heappush(left,[l-r,l,r])
            lenl += 1
        else:
            if l-r>left[0][0]:
                y = heapq.heappop(left)
                heapq.heappush(left,[l-r,l,r])
                score -= y[1]
                score += y[2]
            else:
                score -= l
                score += r
    for k,l,r in b:
        if k>lenr:
            heapq.heappush(right,[r-l,l,r])
            lenr += 1
        else:
            if r-l>right[0][0]:
                y = heapq.heappop(right)
                heapq.heappush(right,[r-l,l,r])
                score -= y[2]
                score += y[1]
            else:
                score -= r
                score += l
    ans.append(score)
printrows(ans)

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

for _ in range(T):
    N = int(input())
    score = 0
    want_left = []
    want_right = []
    for _ in range(N):
        K, L, R = map(int, input().split())
        if K == N:
            score += L
        elif L == R:
            score += L
        elif L > R:
            want_left.append((K, L-R))
            score += R
        else:
            want_right.append((N-K, R-L))
            score += L

    want_left.sort()
    left_q = []
    index = 0
    i = 0
    while index < len(want_left):
        i += 1
        while index < len(want_left) and want_left[index][0] <= i:
            heapq.heappush(left_q, want_left[index][1])
            index += 1
        while len(left_q) > i:
            heapq.heappop(left_q)
    score += sum(left_q)
    
    want_right.sort()
    right_q = []
    index = 0
    i = 0
    while index < len(want_right):
        i += 1
        while index < len(want_right) and want_right[index][0] <= i:
            heapq.heappush(right_q, want_right[index][1])
            index += 1
        while len(right_q) > i:
            heapq.heappop(right_q)
    score += sum(right_q)

    print(score)

Solution (Python):
import sys
sys.setrecursionlimit(10**7) 
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right

from collections import deque, defaultdict


from collections import Counter

from itertools import accumulate,combinations,permutations,product

from heapq import heapify,heappop,heappush


from functools import reduce,lru_cache

from decimal import Decimal

def input(): 
    x=sys.stdin.readline()
    return x[:-1] if x[-1]=="\n" else x
def printe(*x):print("
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
INF=10**6
class BIT():
    def __init__(self, max_n):
        self.size = max_n + 1
        self.tree = [0] * self.size
        self.depth = self.size.bit_length()
        self.tot=0
        
    def initialize(self,seq):
        tree = self.tree
        size = self.size
        self.tot=0
        for i,x in enumerate(seq,1):
            self.tot+=x
            tree[i] += x
            j = i+(i&(-i))
            if j < size:
                tree[j] += tree[i]
        
    def __repr__(self):
        return self.tree.__repr__()
        
    def sum(self,i):
        tree = self.tree
        s = 0
        while i:
            s += tree[i]
            i -= i & -i
        return s
 
    def add(self, i, val):
        tree = self.tree
        size = self.size
        while i < size:
            tree[i] += val
            i += i & -i
        self.tot+=val
    
    def find(self,k):
        if k>self.tot: return self.size
        tree = self.tree; size = self.size
        x,sx = 0,0
        dx = 1 << (self.depth)
        for i in range(self.depth - 1, -1, -1):
            dx = (1 << i)
            if x + dx >= size:
                continue
            y = x + dx
            sy = sx + tree[y]
            if sy < k:
                x,sx = y,sy
        return x + 1

def main():
    mod = 1000000007
    

    N = int(input())
    
    
    
    S = list(tuple(map(int, input().split())) for i in range(N)) 

    def dif(s):
        L=s[1]
        R=s[2]
        return abs(L-R)
    S.sort(key=dif,reverse=1)

    l1=BIT(N)
    l2=BIT(N)
    a=[1]*N
    l1.initialize(a)
    l2.initialize(a)
    ans=0
    for K,L,R in S:
        if L>R:
            t=l1
            la=L
            mi=R
        elif R>L:
            t=l2
            la=R
            mi=L
            K=N-K
        else:
            ans+=R
            continue
        if K==0:
            ans+=mi
            continue
            
        x=t.sum(K)
        if x!=0:
            ins=t.find(x)
            t.add(ins,-1)
            ans+=la
        else:
            ans+=mi
    print(ans)




        



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

Solution (Python):
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
from heapq import heappop,heappush

t = int(readline())
q = list(map(int,read().split()))

now = 0
ans = [0] * t
for cyc in range(t):
    n = q[now]
    klr = q[now+1: now+1+3*n]
    now = now+1+3*n

    it = iter(klr)
    lc = []
    rc = []
    min_p = 0
    for x,y,z in zip(it,it,it):
        if(y==z):
            min_p += y
        elif(y>z):
            min_p += z
            lc.append((x,y-z))
        else:
            min_p += y
            rc.append((n-x,z-y))

    res = min_p
    lc.sort()
    rc.sort()

    for cam in [lc,rc]:
        hq = []
        for i in range(n,0,-1):
            if(len(cam)>0):
                while(cam[-1][0] == i):
                    x,p = cam.pop()
                    heappush(hq,p*-1)
                    if(len(cam)==0):
                        break
            if(hq):
                res += heappop(hq)*-1

    ans[cyc] = res

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

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

t = int(input())

ans = [0]*t
for i in range(t):
    n = int(input())
    plus = [[] for i in range(n)]
    minus = [[] for i in range(n)]
    delta = 0
    for _ in range(n):
        k,l,r = map(int,input().split())
        k -= 1
        ans[i] += r
        if l-r > 0:
            plus[k].append(l-r)
        elif l-r < 0:
            minus[k].append(l-r)
            delta += l-r
    can = 0
    pq = []
    for j in range(n-1,-1,-1):
        while plus[j]:
            heappush(pq,-plus[j].pop())
        if pq:
            delta += -heappop(pq)
            can += 1
    pqm = []
    for j in range(n):
        if j >= can and pqm:
            delta += -heappop(pqm)
        while minus[j]:
            heappush(pqm,minus[j].pop())
    ans[i] += delta
print("\n".join(str(i) for i in ans))

Solution (Python):
class SegTree():
    def segfunc(self, x, y):
        return x + y

    def __init__(self, ide, n, init_val):
        self.ide_ele = ide
        self.num = 2**(n-1).bit_length()
        self.seg = [self.ide_ele] * 2 * self.num
        for i in range(n):
            self.seg[i+self.num-1] = init_val[i]    
        for i in range(self.num-2,-1,-1):
            self.seg[i] = self.segfunc(self.seg[2*i+1],self.seg[2*i+2]) 
    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.segfunc(self.seg[k*2+1], self.seg[k*2+2])
    def query(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.segfunc(res, self.seg[p])
            if q&1 == 1:
                res = self.segfunc(res, self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.segfunc(res, self.seg[p])
        else:
            res = self.segfunc(self.segfunc(res, self.seg[p]), self.seg[q])
        return res

def solve():
    n = int(input())
    camel = [list(map(int, input().split())) for _ in range(n)]
    camel_L = []
    camel_R = []
    for i in range(n):
        if camel[i][1] > camel[i][2]:
            camel_L.append([camel[i][0], camel[i][1], camel[i][2]])
        else:
            camel_R.append([camel[i][0], camel[i][1], camel[i][2]])
    ans = 0
    camel_L.sort(key=lambda x: (x[2]- x[1]))
    camel_R.sort(key=lambda x: (x[1]- x[2]))
    seg = SegTree(0, n, [0]*n)
    nex = [i for i in range(n)]
    for i in range(len(camel_L)):
        k, l, r = camel_L[i]
        q = seg.query(0, k)
        if q < k:
            p = nex[k-1]
            while p != nex[p]:
                pre = p
                p = nex[p]
                nex[pre] = nex[p]-1
            nex[p] = p-1
            seg.update(p, 1)
            ans += l
        else:
            ans += r
    seg = SegTree(0, n, [0]*n)
    nex = [i for i in range(n)]
    for i in range(len(camel_R)):
        k, l, r = camel_R[i]
        q = seg.query(k, n)
        if q < n-k:
            p = nex[k]
            while p != nex[p]:
                pre = p
                p = nex[p]
                nex[pre] = nex[p]+1
            nex[p] = p+1
            seg.update(p, 1)
            ans += r
        else:
            ans += l
    return ans

def main():
    t = int(input())
    ans = [None]*t
    for i in range(t):
        ans[i] = solve()
    for v in ans:
        print(v)

if __name__ == "__main__":
    main()

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


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

    p_li = sorted(p_li, reverse=True)
    l = 0
    q = []
    for i in range(n)[::-1]:
        while l < len(p_li) and p_li[l][0] == i:
            heapq.heappush(q, -p_li[l][1])
            l += 1
        if q:
            val = -heapq.heappop(q)
            ans += val

    m_li = sorted(m_li, reverse=True)
    l = 0
    q = []
    for i in range(n)[::-1]:
        while l < len(m_li) and m_li[l][0] == i:
            heapq.heappush(q, -m_li[l][1])
            l += 1
        if q:
            val = -heapq.heappop(q)
            ans += val
    print(ans)

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

t = int(sys.stdin.buffer.readline())
buf = []
for _ in range(t):
    n = int(sys.stdin.buffer.readline())
    lll = []
    rrr = []
    ans = 0
    for i in range(n):
        k, l, r = map(int, sys.stdin.buffer.readline().split())
        if l >= r:
            lll.append((k, l - r))
            ans += l
        else:
            rrr.append((n - k, r - l))
            ans += r
    lll.sort()
    rrr.sort()
    q = []
    for k, rl in lll:
        if len(q) < k:
            heappush(q, rl)
        else:
            nrl = heappushpop(q, rl)
            ans -= nrl
    q = []
    for k, lr in rrr:
        if len(q) < k:
            heappush(q, lr)
        else:
            nlr = heappushpop(q, lr)
            ans -= nlr

    buf.append(ans)

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

Solution (Python):
import bisect
T=int(input())
class Segtree(object):
    def __init__(self, init_val, N):
        self.func = self.segfunc_max
        self.ide_ele = 0 

        self.num = 2**(N-1).bit_length()
        self.seg = [self.ide_ele]*2*self.num
        self.init_val = init_val

        n = len(self.init_val)
        self.seg[self.num-1:n+self.num-1] = self.init_val[:n]
        
        for i in range(self.num-2,-1,-1) :
            self.seg[i] = self.func(self.seg[2*i+1], self.seg[2*i+2])

    def update(self, k, x):
        k += self.num-1
        self.seg[k] = x
        while k:
            k = (k-1)//2
            self.seg[k] = self.func(self.seg[k*2+1], self.seg[k*2+2])

    def query(self, p, q):
        if q<=p:
            return -1
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if self.seg[p]==0 and self.seg[q]==0:
                return -1
            elif self.seg[q]==0:
                q = (q-1)//2
                res = self.seg[p]
                continue
            else:
                res = self.seg[q]
                p = p//2
                continue
        if p == q:
            
            res = -1
        return res
    def query2(self, p, q):
        if q<=p:
            return self.ide_ele
        p += self.num-1
        q += self.num-2
        res = self.ide_ele
        while q-p>1:
            if p&1 == 0:
                res = self.func(res,self.seg[p])
            if q&1 == 1:
                res = self.func(res,self.seg[q])
                q -= 1
            p = p//2
            q = (q-1)//2
        if p == q:
            res = self.func(res,self.seg[p])
        else:
            res = self.func(self.func(res,self.seg[p]),self.seg[q])
        return res
    def segfunc_max(self, a, b):
        if a >= b:
            return a
        return b

for t in range(T):
    N=int(input())
    KLR = [tuple(map(int,input().split())) for _ in range(N)]
    DKLR2 = [(R-L, K, i) for i,(K,L,R) in enumerate(KLR) if R-L>0]
    DKLR = [(L-R, K, i) for i,(K,L,R) in enumerate(KLR) if R-L<=0]
    DKLR = sorted(DKLR, reverse=True)
    DKLR2 = sorted(DKLR2, reverse=True)
    res = 0
    L1 = len(DKLR)
    L2 = len(DKLR2)
    left = list(range(1,L1+1))
    right = list(range(1,L2+1))
    seg1 = Segtree(left,L1)
    seg2 = Segtree(right,L2)
    
    
    for dv,k,i in DKLR:
        
        if k <= L1:
            idx = seg1.query2(0,k)-1
            
            if idx!=-1:
                seg1.update(idx, 0)
                res += KLR[i][1]
            else:
                res += KLR[i][2]
        else:
            res += KLR[i][1]
    for dv,k,i in DKLR2:
        
        if k >= N-L2:
            idx = seg2.query2(0,N-k)-1
            
            if idx!=-1:
                seg2.update(idx, 0)
                res += KLR[i][2]
            else:
                res += KLR[i][1]
        else:
            res += KLR[i][2]
    
    
    
    
    
    
    
    print(res)

Solution (Python):
import sys
input = lambda: sys.stdin.readline().rstrip()
import heapq  
def calc(A):
    n = len(A)
    c = 0
    h = []
    ret = 0
    for i, aa in enumerate(A):
        for a in aa:
            ret += a
            heapq.heappush(h, a)
            if len(h) > i + 1:
                ret -= heapq.heappop(h)
    return ret

T = int(input())
for _ in range(T):
    N = int(input())
    L = [[] for _ in range(N)]
    R = [[] for _ in range(N)]
    ans = 0
    for _ in range(N):
        k, l, r = map(int, input().split())
        if k == N:
            ans += l
        elif l == r:
            ans += l
        elif l < r:
            ans += l
            R[N-1-k].append(r - l)
        else:
            ans += r
            L[k-1].append(l - r)
    ans += calc(L) + calc(R)
    print(ans)

Solution (Python):
import heapq
def solve():
    N = int(input())
    klr = [list(map(int,input().split())) for _ in range(N)]
    
    ll = []
    lr = []
    for i in range(N):
        if klr[i][1]>klr[i][2]:
            ll.append(klr[i])
        else:
            lr.append(klr[i])

    ansl = 0
    ll.sort(key=lambda x:-x[0])
    j = 0
    cand = []
    for i in range(len(ll)-1,-1,-1):
        while j<len(ll):
            if ll[j][0]-1<i:
                break
            heapq.heappush(cand,[ll[j][2]-ll[j][1],ll[j][0],ll[j][1],ll[j][2]])
            j += 1
        if cand:
            d,k,l,r = heapq.heappop(cand)
            ansl += l
    while cand:
        d,k,l,r = heapq.heappop(cand)
        ansl += r

    ansr = 0
    lr.sort(key=lambda x:x[0])
    j = 0
    cand = []
    for i in range(len(ll),N+1):
        while j<len(lr):
            if lr[j][0]>i:
                break
            heapq.heappush(cand,[-lr[j][2]+lr[j][1],lr[j][0],lr[j][1],lr[j][2]])
            j += 1
        if cand and i!=N:
            d,k,l,r = heapq.heappop(cand)
            ansr += r
    while cand:
        d,k,l,r = heapq.heappop(cand)
        ansr += l
    ans = ansl+ansr
    print(ans)

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

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

t = int(input())
for i in range(t):
    n = int(input())
    C = [list(map(int,input().split())) for i in range(n)]
    L = []
    R = []

    ans = 0
    for i in range(n):
        k = C[i][0]-1
        l = C[i][1]
        r = C[i][2]
        ans += min(l,r)
        if l > r:
            L.append([r-l, k])
        elif l < r:
            R.append([l-r, k+1])

    L.sort(key=lambda x:x[1], reverse=True)
    R.sort(key=lambda x:x[1])

    LQ = []
    ind = 0
    for i in range(n-1,-1,-1):
        while ind < len(L) and L[ind][1] == i:
            heappush(LQ, L[ind])
            ind += 1
        if len(LQ) > 0:
            LL = heappop(LQ)
            ans += -LL[0]

    RQ = []
    ind = 0
    for i in range(n):
        while ind < len(R) and R[ind][1] == i:
            heappush(RQ, R[ind])
            ind += 1
        if len(RQ) > 0:
            RR = heappop(RQ)
            ans += -RR[0]
    
    print(ans)