CodeEff/ECCO huggingface dataset:
# Original solution
def main():
  from collections import deque
  import sys
  input = sys.stdin.readline
  T = int(eval(input()))
  def res_1(lis,ans):
    flag = [False] * (N)
    for klr in lis:
      x = klr[0]
      for _ in range(N):
        if x<0:
          ans += klr[2]
          break
        if flag[x]:
          x -= 1
        else:
          flag[x] = True
          ans += klr[1]
          break
    return ans
  
  def res_2(lis,ans):
    flag = [False] * (N)
    for klr in right:
      x = klr[0] + 1
      for _ in range(N):
        if x>=N:
          ans += klr[1]
          break
        if flag[x]:
          x += 1
        else:
          flag[x] = True
          ans += klr[2]
          break
          
    return ans
  for _ in range(T):
    N = int(eval(input()))
    KLR = [list(map(int,input().split())) for _ in range(N)]
    left = deque([])
    right = deque([])
    ans = 0
    for K,L,R in KLR:
      x = L - R
      if x==0:
        ans += L
      elif x>0:
        left.append([K-1,L,R,x])
      else:
        right.append([K-1,L,R,x])

    left = sorted(left,key = lambda x:x[3],reverse = True)
    right = sorted(right, key = lambda x:x[3])
    ans = res_1(left,ans)
    ans = res_2(right,ans)

    print(ans)
    
main()

# Optimized solution
def main():
  from collections import deque
  import sys
  input = sys.stdin.readline
  from heapq import heapify,heappop,heappush
  T = int(eval(input()))
  for _ in range(T):
    N = int(eval(input()))
    KLR = [list(map(int,input().split())) for _ in range(N)]
    left = deque([])
    right = deque([])
    ans = 0
    for K,L,R in KLR:
      x = L - R
      if x==0:
        ans += L
      elif x>0:
        left.append([K,L,R])
        ans += R
      else:
        right.append([K+1,L,R])
        ans += L

    left = sorted(left)
    right = sorted(right,reverse=True)
      
    S = []
    heapify(S)
    x = 1
    i = 0
    length = len(left)
    while x<=N:
      while i<length:
        klr = left[i]
        if klr[0]==x:
          heappush(S,klr[1]-klr[2])
          i += 1
          
        else:
          break
      
      y = len(S) - x
      if y<=0:
        x += 1
        continue
      else:
        for _ in range(y):
          heappop(S)
          
    ans += sum(S)
    
    S = []
    heapify(S)
    x = N+1
    i = 0
    length = len(right)
    while x>=0:
      while i<length:
        klr = right[i]
        if klr[0]==x:
          heappush(S,klr[2]-klr[1])
          i += 1
 
        else:
          break
      
      y = len(S) + x - N - 1
      if y<=0:
        x -= 1
        continue
      else:
        for _ in range(y):
          heappop(S)    
    ans += sum(S)
    print(ans)
    
main()
# Original solution
from heapq import*
i=input
s=sorted
def f(x):
 s,n,*h=0,len(x)
 while n:
  while x and x[-1][0]>=n:k,l,r=x.pop();heappush(h,(r-l,l,r))
  if h:s+=heappop(h)[1]
  n-=1
 return s+sum(r for _,_,r in x+h)
for _ in'_'*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=list(map(int,i().split()))
  if l>r:x+=(k,l,r),
  else:y+=(n-k,r,l),
 print((f(s(x))+f(s(y))))

# Optimized solution
from heapq import*
i=input
s=sorted
def f(x):
 s,n,*h=0,len(x)
 while n:
  while x and x[-1][0]>=n:k,l,r=x.pop();heappush(h,(r-l,l,r))
  if h:s+=heappop(h)[1]
  n-=1
 return s+sum(r for*_,r in x+h)
for _ in'_'*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=list(map(int,i().split()))
  if l>r:x+=(k,l,r),
  else:y+=(n-k,r,l),
 print((f(s(x))+f(s(y))))
# Original solution
from heapq import*
i=input
def f(x):
 x.sort();s,n,*h=0,len(x)
 while n:
  n-=1
  while x and x[-1][0]>n:k,l,r=x.pop();heappush(h,(r-l,l,r))
  if h:s+=heappop(h)[1]
 return s+sum(r for*_,r in x+h)
for _ in'_'*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:
  k,l,r=list(map(int,i().split()))
  if l>r:x+=(k,l,r),
  else:y+=(n-k,r,l),
 print((f(x)+f(y)))

# Optimized solution
from heapq import*
i=input
for _ in'_'*int(i()):
 n,s,x,*y=int(i()),0,[]
 for _ in'_'*n:
  k,l,r=list(map(int,i().split()))
  if l>r:x+=(k,l,r),
  else:y+=(n-k,r,l),
 for x in(x,y):
  x.sort();n,*h=len(x),
  while n:
   n-=1
   while x and x[-1][0]>n:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
  for*_,r in x+h:s+=r
 print(s)
# Original solution
from heapq import*
i=input
for _ in'_'*int(i()):
 n,s,x,*y=int(i()),0,[];exec('k,l,r=t=[*map(int,i().split())];x+=[t]*(l>r);y+=[(n-k,r,l)]*(l<=r);'*n)
 for x in x,y:
  x.sort();n,*h=len(x),
  while n:
   n-=1
   while x and x[-1][0]>n:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
  for*_,r in x+h:s+=r
 print(s)

# Optimized solution
from heapq import*
i=input
for _ in'_'*int(i()):
 n,s,x,*y=int(i()),0,[]
 for _ in'_'*n:k,l,r=t=[*list(map(int,i().split()))];x+=[t]*(l>r);y+=[[n-k,r,l]]*(l<=r)
 for x in x,y:
  x.sort();n,*h=len(x),
  while n:
   while[[n,0,0]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[1]
   n-=1
  for*_,r in x+h:s+=r
 print(s)
# Original solution
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:k,l,r=t=[*list(map(int,i().split()))];x+=[t]*(l>r);y+=[[n-k,r,l]]*(l<=r)
 for x in x,y:
  x.sort();n,*h=len(x),
  while h+x:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[2-(n>0)]
   n-=1
 print(s)

# Optimized solution
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:k,l,r=t=[*list(map(int,i().split()))];x+=[t]*(l>r);y+=[[n-k,r,l]]*(l<=r)
 for x in x,y:
  x.sort();n,*h=len(x),
  while h or x:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   if h:s+=heappop(h)[~(n>0)]
   n-=1
 print(s)
# Original solution
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:k,l,r=t=[*list(map(int,i().split()))];x+=[t]*(l>r);y+=[[n-k,r,l]]*(l<=r)
 for x in x,y:
  x.sort();n=len(x);h=[(0,0)]*n*2
  while h:
   while[[n]]<x[-1:]:k,l,r=x.pop();heappush(h,(r-l,l,r))
   s+=heappop(h)[~(n>0)];n-=1
 print(s)

# Optimized solution
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:k,l,r=t=[*list(map(int,i().split()))];x+=[t]*(l>r);y+=[[n-k,r,l]]*(l<=r)
 for x in x,y:
  h=[]
  for k,l,r in sorted(x):
   s+=r
   if k:s+=l-r;heappush(h,l-r)
   if len(h)>k:s-=heappop(h)
 print(s)
# Original solution
from heapq import*
i=input
for s in[0]*int(i()):
 n,x,*y=int(i()),[]
 for _ in'_'*n:k,l,r=t=[*list(map(int,i().split()))];x+=[t]*(l>r);y+=[[n-k,r,l]]*(l<=r)
 for x in x,y:h=[];s+=sum(heappush(h,l-r)or l-(k<len(h)and heappop(h))for k,l,r in sorted(x))
 print(s)

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

readline = sys.stdin.readline


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

    left = [[] for _ in range(N)]
    right = [[] for _ in range(N)]
    ans = 0
    for _ in range(N):
        K, L, R = list(map(int, readline().split()))
        if L > R:
            ans += R
            left[K - 1].append(R - L)
        else:
            ans += L
            if 0 <= N - K - 1:
                right[N - K - 1].append(L - R)

    for vec in (left, right):
        hq = []
        n = len(vec)
        for idx in range(N - 1, -1, -1):
            for p in vec[idx]:
                heappush(hq, p)
            if idx < n and hq:
                ans -= heappop(hq)

    return ans


def main():
    T = int(readline())

    ans = [0] * T
    for i in range(T):
        ans[i] = solve()

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


if __name__ == '__main__':
    main()


# Optimized solution
import sys
from heapq import heappush, heappop

readline = sys.stdin.readline


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

    left = [[] for _ in range(N)]
    right = [[] for _ in range(N)]
    ans = 0
    for _ in range(N):
        K, L, R = list(map(int, readline().split()))
        if L > R:
            ans += R
            left[K - 1].append(L - R)
        else:
            ans += L
            if 0 <= N - K - 1:
                right[N - K - 1].append(R - L)

    for vec in (left, right):
        hq = []
        n = len(vec)
        for idx in range(N):
            for p in vec[idx]:
                heappush(hq, p)
            while len(hq) > min(idx + 1, n):
                heappop(hq)

        ans += sum(hq)

    return ans


def main():
    T = int(readline())

    ans = [0] * T
    for i in range(T):
        ans[i] = solve()

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


if __name__ == '__main__':
    main()
# Original solution
import sys
from heapq import heappush, heappop

readline = sys.stdin.readline


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

    left = [[] for _ in range(N)]
    right = [[] for _ in range(N)]
    ans = 0
    for _ in range(N):
        K, L, R = list(map(int, readline().split()))
        if L > R:
            ans += R
            left[K - 1].append(L - R)
        else:
            ans += L
            if 0 <= N - K - 1:
                right[N - K - 1].append(R - L)

    for vec in (left, right):
        hq = []
        n = len(vec)
        for idx in range(N):
            for p in vec[idx]:
                heappush(hq, p)
            while len(hq) > min(idx + 1, n):
                heappop(hq)

        ans += sum(hq)

    return ans


def main():
    T = int(readline())

    ans = [0] * T
    for i in range(T):
        ans[i] = solve()

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


if __name__ == '__main__':
    main()


# Optimized solution
import sys
from heapq import heappush, heappop

readline = sys.stdin.readline


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

    left = [[] for _ in range(N)]
    right = [[] for _ in range(N)]
    ans = 0
    for _ in range(N):
        K, L, R = list(map(int, readline().split()))
        if L > R:
            ans += R
            left[K - 1].append(L - R)
        else:
            ans += L
            if 0 <= N - K - 1:
                right[N - K - 1].append(R - L)

    for vec in (left, right):
        hq = []
        n = len(vec)

        for i in range(n):
            for p in vec[i]:
                heappush(hq, p)
            while len(hq) > i + 1:
                heappop(hq)

        for i in range(n, N):
            for p in vec[i]:
                heappush(hq, p)
            while len(hq) > n:
                heappop(hq)

        ans += sum(hq)

    return ans


def main():
    T = int(readline())

    ans = [0] * T
    for i in range(T):
        ans[i] = solve()

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


if __name__ == '__main__':
    main()
# Original solution
n = eval(input())
numbers = input().split()
print((' '.join(numbers[::-1])))

# Optimized solution
n = eval(input())
numbers = list(input().split())
print((" ".join(numbers[::-1])))
# Original solution
input()
i = list(map(int, input().split()))
i.reverse()
for j in range(len(i)) :
    if j != 0 :
        print(' ', end = '')
    print(i[j], end = '')
print()


# Optimized solution
eval(input())
data = input().split()
data.reverse()
print((' '.join(data)))
# Original solution
eval(input())
a = list(input().split())
a.reverse()
print((" ".join(a)))

# Optimized solution
eval(input())
print((" ".join(reversed(input().split()))))
# Original solution
import sys

n = int( sys.stdin.readline() )
nums = sys.stdin.readline().rstrip().split( " " )
nums.reverse()
output = []
for i in range( n ):
	output.append( nums[i] )
	if i < (n-1):
		output.append( " " )
print(( "".join( output ) ))

# Optimized solution
import sys

n = int( sys.stdin.readline() )
nums = sys.stdin.readline().rstrip().split( " " )
nums.reverse()
print(( " ".join( nums ) ))
# Original solution
n = int(input())
a = list(map(int,input().split()))
a.reverse()
for i in range(n-1):
    print(a[i],end = " ")
print(a[n-1])


# Optimized solution
n =int(input())
a = list(map(int,input().split()))
a.reverse()
for i in range(n):
    if i!=n-1:
        print(a[i],end=" ")
    else:
        print(a[i])
# Original solution
n = int(input())
ls = list(map(int,input().split()))
print(' '.join(map(str,ls[::-1])))

# Optimized solution
n = int(input())
print(' '.join(input().split()[::-1]))
# Original solution
#coding:utf-8
#1_6_A 2015.4.1
n = int(input())
numbers = list(map(int,input().split()))

for i in range(n):
    if i == n - 1:
        print(numbers[-i-1])
    else:
        print(numbers[-i-1], end = ' ')


# Optimized solution
#coding:utf-8
#1_6_A 2015.4.1
eval(input())
numbers = input().split()
numbers.reverse()
print((' '.join(numbers)))
# Original solution
n,k = list(map(int,input().split()))

pList = list(map(int,input().split()))

cList = list(map(int,input().split()))

cSum = sum(cList)
p = dict()
c = dict()

for i in range(n):
    p[i] = pList[i]
    c[i] = cList[i]

highScore = min(cList)
for i in range(n):
    count = 0
    zahyou = i
    score = 0
    zumi =set()
    loop = False
    while count < k:
        if not(loop):
            if zahyou in zumi:
                loop = True
                if score > 0:
                    score += score * ((k // count) - 2)
                    count += ((k // count) - 2) * count
                else:
                    break
        zumi.add(zahyou)
        zahyou = p[zahyou] - 1
        score += c[zahyou]
        count += 1
        if highScore < score:
            highScore = score

print(highScore)

# Optimized solution
n,k = list(map(int,input().split()))

pList = list(map(int,input().split()))

cList = list(map(int,input().split()))

cSum = sum(cList)
p = dict()
c = dict()

for i in range(n):
    p[i] = pList[i]
    c[i] = cList[i]

highScore = min(cList)
for i in range(n):
    count = 0
    zahyou = i
    score = 0
    zumi =zahyou
    loop = False
    while count < k:
        if not(loop):
            if zahyou == zumi and count != 0:
                loop = True
                if score > 0:
                    score += score * ((k // count) - 2)
                    count += ((k // count) - 2) * count
                else:
                    break
        zahyou = p[zahyou] - 1
        score += c[zahyou]
        count += 1
        if highScore < score:
            highScore = score

print(highScore)
# Original solution
import sys
import copy
input = sys.stdin.readline


N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
C=list(map(int,input().split()))

ans=-1*(10**10)
for i in range(N):
    tmp=0
    pos=i
    count=0
    while count<K:    
        #print(pos,P[pos])
        tmp+=C[P[pos]-1]
        if tmp>ans:
            ans=tmp
        
        pos=P[pos]-1
        count+=1

print(ans)

# Optimized solution
import sys
import copy
input = sys.stdin.readline


N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
C=list(map(int,input().split()))

ans=-1*(10**10)

if K<10000000:
    for i in range(N):
        tmp=0
        pos=i
        count=0
        while count<K:    
            #print(pos,P[pos])
            tmp+=C[P[pos]-1]
            if tmp>ans:
                ans=tmp
            
            pos=P[pos]-1
            count+=1
     
    print(ans)
else:
    
    for i in range(N):
        tmp=0
        pos=i
        gpos=i
        count=0
        while count<K:    
            #print(pos,P[pos])
            tmp+=C[P[pos]-1]
            if tmp>ans:
                ans=tmp
            
            
            pos=P[pos]-1
            count+=1
            if pos==gpos:
                divide=K//count-1
                tmp=tmp*divide
                count=count*divide
                gpos=10**10
            
    
    print(ans)
# Original solution
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
C = list(map(int, input().split()))
INF = 10**9+1

def solve():
    cycles = []
    memo = [False] * N
    i = 0
    while i < N-1:
        cycle = []
        j = i
        while not memo[j]:
            cycle.append(j)
            memo[j] = True
            j = P[j] - 1
        k = i
        for i in range(k, N):
            if not memo[i]:
                break
        cycles.append(cycle)

    ans = -INF

    for cycle in cycles:
        n = len(cycle)
        # q, r = divmod(K-1, n)
        # r += 1
        memo = [-INF] * n
        for i in range(n):
            s = 0
            for j in range(n):
                s += C[cycle[(i+j)%n]]
                memo[j] = max(memo[j], s)
        tmpmax = -INF
        imax = -1
        if K < n:
            for i in range(K):
                if tmpmax < memo[i]:
                    tmpmax = memo[i]
                    imax = i+1
        else:
            if memo[-1] > 0:
                for i in range(n):
                    q = (K-i-1) // n
                    tmpmax = max(tmpmax, memo[i] + memo[-1] * q)
            else:
                for i in range(n):
                    tmpmax = max(tmpmax, memo[i])

        ans = max(ans, tmpmax)
    return ans

if __name__ == "__main__":
    print((solve()))


# Optimized solution
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
C = list(map(int, input().split()))
INF = 10**9+1

def solve():
    ans = -INF

    for i in range(N):
        memo = [0] * (N+1)
        j = 0
        p = i
        while j < N:
            memo[j+1] = memo[j] + C[p]
            p = P[p] - 1
            j += 1
            if p == i:
                break
        tans =-INF
        if memo[j] > 0:
            for k in range(j):
                q = (K-k-1) // j
                tans = max(tans, memo[k+1] + memo[j] * q)
        else:
            for k in range(min(K, j)):
                tans = max(tans, memo[k+1])

        ans = max(ans, tans)
    return ans

if __name__ == "__main__":
    print((solve()))
# Original solution
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
P = [p - 1 for p in P]
C = list(map(int, input().split()))

vis = [False] * N
ans = [-float('inf')] * N

for root in range(N):
    if vis[root]:
        continue
    vis[root] = True

    cycle = [root]
    costs = [C[root]]
    u = P[root]
    while u != root:
        cycle.append(u)
        costs.append(C[u])
        u = P[u]

    # print('-' * 10)
    # print(cycle)
    # print(costs)

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        cnt = 0
        for step in range(1, min(L, K) + 1):
            cnt += costs[(i + step) % L]
            val1 = cnt
            val2 = cnt + (K - step) // L * S
            ans[v] = max(ans[v], val1, val2)

print((max(ans)))



# Optimized solution
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
P = [p - 1 for p in P]
C = list(map(int, input().split()))

vis = [False] * N
ans = [-float('inf')] * N

for root in range(N):
    if vis[root]:
        continue
    vis[root] = True

    cycle = [root]
    costs = [C[root]]
    u = P[root]
    vis[u] = True
    while u != root:
        cycle.append(u)
        costs.append(C[u])
        u = P[u]
        vis[u] = True

    # print('-' * 10)
    # print(cycle)
    # print(costs)

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        cnt = 0
        for step in range(1, min(L, K) + 1):
            cnt += costs[(i + step) % L]
            val1 = cnt
            val2 = cnt + (K - step) // L * S
            ans[v] = max(ans[v], val1, val2)

print((max(ans)))
# Original solution
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
P = [p - 1 for p in P]
C = list(map(int, input().split()))

vis = [False] * N
ans = [-float('inf')] * N

for root in range(N):
    if vis[root]:
        continue

    cycle = [root]
    costs = [C[root]]
    u = P[root]
    while u != root:
        cycle.append(u)
        costs.append(C[u])
        u = P[u]
    
    for u in cycle:
        vis[u] = True

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        # Rewrite [1, K] as form q * L + r, :
        # 0L + 1, 0L + 2, ..., 0L + L
        # 1L + 1, 1L + 2, ..., 1L + L
        # ⋮ 
        # tL + 1, tL + 2, ... (t = floor((K - r) / L))

        # We can ignore 1L + r, 2L + r, ..., (t - 1) * L + r
        # since the total cost of loop is either positive or negative
        # When positive, 0L + r < 1L + r < 2L + r < tL + r
        # When negative, the answer should be 0L + r

        cnt = 0
        for rem in range(1, min(L, K) + 1):
            cnt += costs[(i + rem) % L]
            val1 = cnt
            val2 = cnt + (K - rem) // L * S
            ans[v] = max(ans[v], val1, val2)

print((max(ans)))



# Optimized solution
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
P = [p - 1 for p in P]
C = list(map(int, input().split()))

vis = [False] * N
ans = [-float('inf')] * N

for root in range(N):
    if vis[root]:
        continue

    cycle = [root]
    costs = [C[root]]
    u = P[root]
    while u != root:
        cycle.append(u)
        costs.append(C[u])
        u = P[u]
    
    for u in cycle:
        vis[u] = True

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        # Rewrite [1, K] as form q * L + r,
        # 0L + 1, 0L + 2, ..., 0L + L
        # 1L + 1, 1L + 2, ..., 1L + L
        # ⋮ 
        # tL + 1, tL + 2, ... 

        # We can ignore 1L + r, 2L + r, ..., (t - 1) * L + r
        # since the total cost of loop is either > 0 or <= 0
        # When > 0, 0L + r < 1L + r < 2L + r < tL + r
        # When <= 0, the answer should be 0L + r

        if S > 0:
            rem_cost = 0
            for rem in range(1, min(L, K) + 1):
                rem_cost += costs[(i + rem) % L]
                t = (K - rem) // L
                ans[v] = max(ans[v], rem_cost + t * S)
        else:
            rem_cost = 0
            for rem in range(1, min(L, K) + 1):
                rem_cost += costs[(i + rem) % L]
                ans[v] = max(ans[v], rem_cost)

print((max(ans)))