Harryxun/stf_run huggingface dataset:
N, M = map(int, input().split())

graph = [dict() for _ in range(N)]
for i in range(M):
    x, y = map(int, input().split())
    graph[x-1][y-1] = 1

dp = [0 for _ in range(N)]

def dfs(num_v):
    if len(graph[num_v]) == 0:
        return
    for to in graph[num_v].keys():
        dp[to] = max(dp[to], dp[num_v] + 1)
        dfs(to)

ans = 0
for i in range(N):
    dfs(i)
    ans = max(ans, max(dp))
print(ans)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)

N, M = map(int, input().split())
graph = [dict() for _ in range(N)]

for i in range(M):
    x, y = map(int, input().split())
    graph[y - 1][x - 1] = 1

dp = [0 for _ in range(N)]


def dfs(u):
    if dp[u] != 0:
        return dp[u]
    max_dis = 0
    for f in graph[u].keys():
        if max_dis < dfs(f) + 1:
            max_dis = dfs(f) + 1

    dp[u] = max_dis
    return dp[u]


for i in range(N):
    dfs(i)
print(max(dp))
A, B, C = map(int, input().split())
S = sum(A,B,C)
print(max(S+9*A, S+9*B, S+9*C))

### FIXED CODE ###

A, B, C = map(int, input().split())
S = A+B+C
print(max(S+9*A, S+9*B, S+9*C))
n = int(input())
p = [int(i) for i in input().split()]
count = 0
for i in range(1,n):
    if i+1 == p[i]:
        cha = p[i-1]
        p[i-1] = p[i]
        p[i] = cha
        count+=1
if n == p[n-1]
    count+=1
print(count)

### FIXED CODE ###

n = int(input())
p = [int(i) for i in input().split()]
count = 0
for i in range(n - 1):
    if i+1 == p[i]:
        p[i],p[i+1] = p[i+1],p[i]
        count+=1
if n == p[n-1]:
    count+=1
print(count)
k = int(input())
s = 7
if k%2 == 0:
	print(-1)
elif k%5 == 0:
	print(-1)
else:
	while s%k != 0:
		s = 10*s+7
		s = str(s)
	print(len(s))

### FIXED CODE ###

import sys

k = int(input())

a = 0

for i in range(1, k+1):
	a = (a*10+7)%k
	if a == 0:
		print(i)
		sys.exit()
print(-1)
a,b=intput().split()
b=b*100
print(a*b/100)

### FIXED CODE ###

from decimal import Decimal
a,b=map(Decimal, input().split())
print(int(a*b))
import sys
sys.setrecursionlimit(10 ** 6)
def input():
    return sys.stdin.readline()[:-1]

N,Q=map(int,input().split())
graph=[[]for _ in range(N)]
point=[0]*N
for _ in range(N-1):
    a,b=map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
for _ in range(Q):
    a,b=map(int,input().split())
    a=a-1
    point[a]=point[a]+b

def dfs(now,prev=-1):
    for next in graph[now]:
        if next==prev:
            continue
        point[next]=point[next]+point[now]
        dfs(next,now)
dfs(0)
print(*point)

### FIXED CODE ###

a=int(input())
s=input()
if(a>=3200):
    print(s)
else:
    print("red")
N = int(input())
s = 0
for i in range(0,2):
if N[i] = 1:
    s = s + 1
print(s)
   

### FIXED CODE ###

A = input()
s = 0
for i in range(len(A)):
  if A[i]=="1":
    s = s + 1
print(s)
import numpy as np
from scipy import signal

N = int(input())
H = list(map(int, input().split(" ")))

H = np.array(H)

ans = 'Yes'
min_ind = signal.argrelmin(H)[0]
tmp_ind = 0
for ind in min_ind:
    
    if H[tmp_ind:ind].max() > H[ind]+1:
        ans = 'No'
        break
    tmp_ind = ind

if H[tmp_ind:-1].max() > H[-1]+1:
    ans = 'No'

print(ans)



### FIXED CODE ###


A, B, C = map(int,input().split(" "))

if C+B > A:
    d = (C+B)-A
else:
    d = 0

print(d)
import math
n=input()
print(math.ceil(n/2)/n)

### FIXED CODE ###

import math
n=int(input())
print(math.ceil(n/2)/n)
import math

n,k = map(int, input().split())

def main(i):
  blue = int(math.factorial(k-1) / (math.factorial(i-1) * math.factorial(k-i)))
  red = int(math.factorial(n-k+1) / (math.factorial(n-k+1-i) * math.factorial(i)))
  print((blue*red) % (10**9 + 7))

for i in range(1, k+1)):
  if i > min(k+1, n-k+2):
    print('0')
  else:
   main(i)

### FIXED CODE ###

import math
 
n,k = map(int, input().split())
 
def main(i):
  blue = math.factorial(k-1) // (math.factorial(i-1) * math.factorial(k-i))
  red = math.factorial(n-k+1) // (math.factorial(n-k+1-i) * math.factorial(i))
  print((blue*red) % (10**9 + 7))
 
for i in range(1, k+1):
  if i > n-k+1:
    print('0')
  else:
   main(i)
import numpy as np

n, m = map(int, input().strip().split())
a = np.zeros((n,m), dtype = int)
b = np.zeros((m,1), dtype = int)
c = np.zeros((n,1), dtype = int)

for i in range(n):
    a[i] = list(map(int, input().strip().split()))
for i in range(m):
    b[i] = int(input())

c = a.dot(b)

for i in range(n):
    print(c[i][0])

### FIXED CODE ###

n, m = map(int, input().strip().split())
a = [[0 for j in range(m)] for i in range(n)]
b = [[0] for j in range(m)]
c = [[0] for j in range(n)]

for i in range(n):
    a[i] = list(map(int, input().strip().split()))

for i in range(m):
    b[i] = [int(input())]


for i in range(n):
    for j in range(m):
        c[i][0] += a[i][j]*b[j][0]
    print(c[i][0])
k, s = int(input().split())
count = 0

for i in range(k):
    x = i
    for j in range(k):
        y = j
        for l in range(k):
            z = l
            if x + y + z == s:
                count += 1
print(count)


### FIXED CODE ###

k, s = map(int, input().split())
count = 0

for x in range(k + 1):
    for y in range(k + 1):
        if (s - x - y >= 0 and s - x - y <= k):
            count += 1

print(count)
def MAXI(a):
    m=max(a)
    for i in range(3):
        if a[i]==m:
            id=i
    return m,id



tot=0
N=int(input())
i=0
while i<N:
    
    if i==0:
        x=[int(a) for a in input().split()]
        m,id=MAXI(x)
        tot+=m
        i=i+1
    else:
        x=[int(a) for a in input().split()]
        y=[int(a) for a in input().split()]
        i=i+2
        MAX=0
        for j in range(3):
            if j!=id:
                for k in range(3):
                    if k!=j:
                        s=x[j]+y[k]
                        if s>MAX:
                            MAX=s
                            id1=k
                        
        tot+=MAX
        id=id1
                            
        
print(tot)
    


### FIXED CODE ###

def LIST():
    return list(map(int, input().split()))
N = int(input())
arr = [LIST() for _ in range(N)]
dp = [[arr[0][0],arr[0][1],arr[0][2]],[0,0,0]]
l=1
p=0
for i in range(1, N):
    for j in range(3):
        for k in range(3):
            if j == k: continue
            a1=dp[p][j]
            a2=arr[i][k]
            a3=a1+a2
            dp[l][k] = max(dp[l][k], dp[p][j] + arr[i][k])
    l=l^1
    p=p^1
            
print(max([dp[p][j] for j in range(3)]))
N, K = map(int, input().split())
flag = [for 1 in range(N)]
for i in range(K):
  input()
  for j in map(int,input().split()):
    flag[j-1] = 0
sum(flag)


### FIXED CODE ###

N, K = map(int, input().split(" "))
flag = [1 for i in range(N)]
for i in range(K):
  input()
  for j in map(int,input().split(" ")):
    flag[j-1] = 0
print(sum(flag))
x = input()
t = int(x)
x2 = input()
n = list(map(int, x2.split(" ")))


def main():
  p = 1
  for v in t:
    p *= n[v]
    if (p >= 10 **18):
      print("-1")
      return
  print(p)

main()


### FIXED CODE ###

x = input()
t = int(x)
x2 = input()
n = list(map(int, x2.split(" ")))


def main():
  if 0 in n:
    print(0)
    return
  p = 1
  for v in range(t):
    p *= n[v]
    if (p > 10 **18):
      print("-1")
      return
  print(p)

main()
z,v,a=input,range,print
h,w,k=map(int,z().split())
r,s,t,u=map(lambda x:int(x)-1,z().split())
b=[z()for _ in v(h)]
l=[[-1]*w for _ in v(h)]
l[r][s]=0
from collections import*
d=deque([(r,s)])
while d:
  x,y=d.popleft()
  if(x==t)&(y==u):exit(a(l[x][y]))
  for e,f in[[1,0],[-1,0],[0,-1],[0,1]]:
    for i in v(1,k+1):
      if not((0<=(p:=(x+e*i))<h)&(0<=(q:=(y+f*i))<w))or b[p][q]=="@" or 0<=l[p][q]<=l[x][y]:break
      if l[p][q]==-1:d+=[(p,q)];l[p][q]=l[x][y]+1
a(-1)

### FIXED CODE ###

import sys
inf=1000002
sys.setrecursionlimit(inf)
from collections import deque
h,w,k=map(int,input().split())
x1,y1,x2,y2=map(int,input().split())
c=[input() for i in range(h)]
dp=[[inf if c[i][j]=="." else -1 for j in range(w)] for i in range(h)]
now=deque()
now.append([x1-1,y1-1])
dp[x1-1][y1-1]=0
#kの更新が遅い
def bfs(d):
    global h,w,k,dp,now,x2,y2
    l=len(now)
    if l==0:
        return
    dp_sub=deque()
    cand=set()
    for i in range(l):
        x,y=now.popleft()
        for j in range(1,min(k+1,w-y)):
            if dp[x][y+j]==inf:
                dp_sub.append([x,y+j,d])
                #dp[x][y+j]=d
                cand.add((x,y+j))
                #now.append([x,y+j])
            else:
                break
        for j in range(1,min(k+1,y+1)):
            if dp[x][y-j]==inf:
                dp_sub.append([x,y-j,d])
                #dp[x][y-j]=d
                cand.add((x,y-j))
                #now.append([x,y-j])
            else:
                break
        for j in range(1,min(k+1,h-x)):
            if dp[x+j][y]==inf:
                dp_sub.append([x+j,y,d])
                #dp[x+j][y]=d
                cand.add((x+j,y))
                #now.append([x+j,y])
            else:
                break
        for j in range(1,min(k+1,x+1)):
            if dp[x-j][y]==inf:
                dp_sub.append([x-j,y,d])
                #dp[x-j][y]=d
                cand.add((x-j,y))
                #now.append([x-j,y])
            else:
                break
    while dp_sub!=deque([]):
        e=dp_sub.popleft()
        dp[e[0]][e[1]]=e[2]
    for i in cand:
        now.append(i)
    bfs(d+1)
bfs(1)
print(dp[x2-1][y2-1] if dp[x2-1][y2-1]!=inf else -1)
n = input()
s = input()
print(s.count("ABC")

### FIXED CODE ###

n = input()
s = input()
print(s.count("ABC"))
li = list(map(int,input().split()))
mtx = [[] for _ in range(li[0])]
li_sum = []

for i in range(li[0]):
    a = input()
    mtx[i] = list(map(int,a.split()))
    print(mtx,end='')
    print(' ' ,sum(mtx[i]),sep='')
    
    for j in range(li[j]):
        li_sum[j] += mtx[i][j]
    li_sum[j] += sum(mtx[i])

print(' '.join(map(str,li_sum)))


### FIXED CODE ###

l, c = map(int, input().split())
tbl = [[] for _ in range(l)]
li_sum = [0 for _ in range(c+1)]

for i in range(l):
  a = input()
  tbl[i] = list(map(int, a.split()))
  print(a, end='')
  print(' ', sum(tbl[i]), sep ='')

  for j in range(c):
    li_sum[j] += tbl[i][j]
  li_sum[c] += sum(tbl[i])

print(' '.join(map(str, li_sum)))
x, y = map(int, input().split())

ans = 'No'

for i in range(x + 1):
    j = x - a
    if (j*2 + i*4 == y):
        ans = "Yes"):
print(ans)


### FIXED CODE ###

x, y = map(int, input().split())

ans = 'No'

for i in range(x + 1):
    j = x - i
    if (j*2 + i*4 == y):
        ans = "Yes"
print(ans)
#A-Good Integer(ABC079)
N=input()
if N[1]==N[2]and set(N)<3:
    print("Yes")
else:
    print("No")

### FIXED CODE ###

#A-Good Integer(ABC079)
N=str(input())
if len(set(N[0:3]))==1 or len(set(N[1:4]))==1:
    print("Yes")
else:
    print("No")
def gcd(a, b):
 if a < b:
    a, b = b, a
 if b == 0:
    return a
 c = a % b
 return gcd(b, c)
def lcm(a,b):
  return float(a*b/gcd(a,b))

N = int(input())
ans = 1
for i in range(N):
    t = float(input())
    ans = lcm(t,ans)

print(ans)

### FIXED CODE ###

N = int(input())
T = [int(input()) for i in range(N)]

from functools import reduce
from fractions import gcd

def lcm(a,b):
  return a*b //gcd(a,b)

print(reduce(lcm,T))
import numpy as np

N,K = [int(i) for i in input().split()]
n = np.array([int(i) for i in input().split()])
n=np.sort(n)

mn = n[np.where(n<0)]
mz = n[np.where(n==0)]
mp = n[np.where(n>0)]

#cn = len(mn)
#cp = len(mp)
#cz = len(mz)
#tcn = cn*cp

#if cn*cp < K <= cn*cp + (N-cz)*cz + cz*(cz-1)//2:
#    print(0)
#    exit(0)

M = 10**18
m = -1*M-1
pos = 0

while M-m > 1:
    a = 0
    pos=(M+m)//2
    a+=np.searchsorted(n,pos//mp,side="right").sum()
    a+=cz*N
    a+=N*len(mn) - np.searchsorted(n,-(-pos//mn),side="left").sum()
    a-=np.count_nonzero(n*n <= pos)
    a=a//2
    if a >= K:
        M=pos
    else:
        m=pos
#print(M,m)
print(M)


### FIXED CODE ###

import numpy as np

N,K = [int(i) for i in input().split()]
n = np.array([int(i) for i in input().split()])
n=np.sort(n)

mn = n[np.where(n<0)]
mz = n[np.where(n==0)]
mp = n[np.where(n>0)]

#cn = len(mn)
##cp = len(mp)
#cz = len(mz)
#tcn = cn*cp

#if cn*cp < K <= cn*cp + (N-cz)*cz + cz*(cz-1)//2:
#    print(0)
#    exit(0)

M = 10**18
m = -1*M-1
pos = 0

while M-m > 1:
    a = 0
    pos=(M+m)//2
    a+=np.searchsorted(n,pos//mp,side="right").sum()
    if pos >= 0: a+=len(mz)*N
    a+=N*len(mn) - np.searchsorted(n,-(-pos//mn),side="left").sum()
    a-=np.count_nonzero(n*n <= pos)
    a=a//2
    if a >= K:
        M=pos
    else:
        m=pos
#print(M,m)
print(M)
N = int(input().split())

print(N//2) if N%2==0 else print(N//2 +1)

### FIXED CODE ###

N = int(input())

print(N//2) if N%2==0 else print(N//2 +1)
r,g,b,n=list(map(int,input().split()))
i,j,k=0,0,0
R,G,B=0,0,0
c=0
while R<n:
    R=r*i
    while G<=n-R:
        G=g*j
        B,k=0,0
        while B<=n-R-G:
            B=b*k
            if n-R-G-B==0:
                c+=1
            k+=1
        j+=1
    i+=1
    G,j=0,0
print(c)


### FIXED CODE ###

n,k=list(map(int,input().split()))
print(n-k+1)
import sys
input = sys.stdin.readline

n, m = map(int, input().split())
a = sorted(list(map(int, input().split())))
bc = sorted([list(map(int, input().split())) for i in range(m)], key = itemgetter(1), reverse=True)

ans = 0
for i in range(n):
    now = a[i]
    for rep, con in enumerate(bc):
        if now < con[1] and bc[rep][0] != 0:
            ans += con[1]
            bc[rep][0] -= 1
            break

    else:
        ans += now + sum(a[i+1:])
        break

print(ans)

### FIXED CODE ###

n, m = map(int, input().split())
lr = [list(map(int, input().split())) for i in range(m)]

max_l = float("-inf")
min_r = float("inf")

for l, r in lr:
    max_l = max(max_l, l)
    min_r = min(min_r, r + 1)

ans = min_r-max_l
print("0" if ans <= 0 else ans if ans < n else n)
# -*- coding: utf-8 -*-

n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

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

days_left = [1] * (m + 2)
ans = 0
for a, b in ab:
    i = a
    while days_left[i] == 0:
        i += 1
    if i == m + 1:
        continue
    days_left[i] = 0
    ans += b

print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-

import heapq


class MaxHeap:
    def __init__(self, li):
        self.heap = [-e for e in li]
        heapq.heapify(self.heap)

    def push(self, val):
        heapq.heappush(self.heap, -val)

    def pop(self):
        return -heapq.heappop(self.heap)

    def __len__(self):
        return len(self.heap)


n, m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(n)]

ab.sort()

h = MaxHeap([])

i = 0
ans = 0
for day in range(1, m + 1):
    while i < n and ab[i][0] <= day:
        h.push(ab[i][1])
        i += 1
    if len(h) == 0:
        continue
    ans += h.pop()

print(ans)
import sys
import bisect
import math
input = sys.stdin.readline

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

mc = max(l)[1]
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]

for t in l:
    if len(t) != 2:
        sys.exit()
    x, y = t[0], t[1]
    p = 0
    if 0 <= x - 1:
        p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)


### FIXED CODE ###

import sys
import bisect
import math
input = sys.stdin.readline

n = int(input())
l = [list(map(int, input().split())) for _ in range(n)]

mc = 0
for v in l:
    mc = max(mc, v[1])
mc_sqrt = math.sqrt(mc)

prime = [i for i in range(2, mc + 1)]
c = 0
while True:
    if c >= len(prime):
        break
    t = prime[c]
    prime = [v for v in prime if v == t or v % t != 0]
    c = c + 1
    if c >= mc_sqrt:
        break
        
cum = [0 for i in range(mc + 1)]
for i in range(len(cum)):
    prime_index = bisect.bisect_left(prime, i)
    
    n2 = (i + 1) / 2
    prime_index2 = bisect.bisect_left(prime, n2)
    if len(prime) > prime_index and len(prime) > prime_index2 and prime[prime_index] == i and prime[prime_index2] == n2:
        cum[i] = cum[i - 1] + 1
    else:
        if i - 1 < 0:
            cum[i] = 0
        else:
            cum[i] = cum[i - 1]

for t in l:
    x, y = t[0], t[1]
    p = 0
    if 0 <= x - 1:
        p = cum[x] - cum[x - 1]
    if x != y:
        p += cum[y] - cum[x]
    print(p)
N=list(input())

if N[2]=="2" or "4" or "5" or "7" or "9":
    print("hon")
if N[2]=="0" or "1" or "6" or "8":
    print("pon")
if N[2]=="3":
    print("bon")


### FIXED CODE ###

n=list(input())

n==n.reverse()

if (n[0]=="2" or n[0]=="4" or n[0]=="5" or n[0]=="7" or n[0]=="9"):
    print("hon")
elif (n[0]=="0" or n[0]=="1" or n[0]=="6" or n[0]=="8"):
    print("pon")
elif (n[0]=="3"):
    print("bon")
a,b,c=map(int,input(),split())
d=0

for n=range(1,b+1):
    if n*a%b==c:
        d=d+1
    else:
        d=d:
if d>0:
    print("YES")
else:
    print("NO")


### FIXED CODE ###

a,b,c = map(str,input().split())
 
if a[-1]==b[0] and b[-1]==c[0]:
    print("YES")
else:
    print("NO")
from collections import Counter
n=int(input())
a=list(map(int,input().split()))
b=Counter(a)
t=[]
for _ in b.most_common(100):
  t.append(len([i for i in a if _[0]-1<i<_[0]+3]))
  t.append(len([i for i in a if _[0]-2<i<_[0]+2]))
  t.append(len([i for i in a if _[0]-3<i<_[0]+1]))
print(max(t))

### FIXED CODE ###

x,t=map(int,input().split())
print(x-t if x-t>0 else 0)
prev_t = 0
prev_x = 0
prev_y = 0

n = int(input())
for _ in range(n):
  t, x, y = map(int, input().split())
  dist = (x - prev_x) + (y - prev_y)
  time = t - prev_t
  if dist != time:
    ans = False
    break
  
  prev_x = x
  prev_y = y
  prev_t = t
    
if not ans:
  print('No')
else:
  print('Yes')
  



### FIXED CODE ###

prev_t = 0
prev_x = 0
prev_y = 0

n = int(input())
ans = True
for _ in range(n):
    t, x, y = map(int, input().split())
    dist = (x - prev_x) + (y - prev_y)
    time = t - prev_t
    if dist > time or dist % 2 != time % 2:
        ans = False
        break

    prev_x = x
    prev_y = y
    prev_t = t

if not ans:
    print('No')
else:
    print('Yes')
a = raw_input().lower()
s = 0
while True:
    b = raw_input().lower()
    if b == 'END_OF_TEXT':
        break
    s += b.count(a)
print s

### FIXED CODE ###

a = raw_input().lower()
s = 0
while True:
    b = raw_input()
    if b == 'END_OF_TEXT':
        break
    b = b.split()
    b = map(str.lower,b)
    s += b.count(a)
print s
print(sum(range(int(input())+1))

### FIXED CODE ###

print(sum(range(int(input())+1)))
while True:
  H,W = map(int, input().split())
  if H == 0 and W == 0:
    break
  if i in range(round(H/2)):
    print(("#"+".")*round(W/2))
  elif i in range(int(H/2)):
    print(("."+"#")*round(W/2))    


### FIXED CODE ###

while True:
    (H,W) = [int(i) for i in input().split()]
    if H==W==0:
        break
    for i in range(H):
        for j in range(W):
            if (i+j)%2==0: print('#',end="")
            else: print('.',end="")
        print('')
    print('')
n, b, a = map(int, input().split())
print(n // (a + b) * b + min(n % (a + b), b)

### FIXED CODE ###

def count_balls(n, b, a):
	if b == 0:
		return 0
	
	num = n // (a + b)
	mod = n % (a + b)
	if mod != 0:
		if mod < b:
			return num * b + mod
		else:
			return num * b + b
	else:
		return num * b

n, b, a = map(int, input().split())
print(count_balls(n, b, a))
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):
            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 L[i][0]==len(hR):
            heapq.heappushpop(hR,R[i][1])
    print(ans+sum(hL)+sum(hR))        
    
    

### FIXED CODE ###

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))
inf = float('inf')
n,k=map(int,input().split())
h = list(map(int,input().split()))
dp=[0] + [inf] *(n-1)#初期化
for i in range(1,n):
    for j in range(1,k+1):#iからj離れた場所から来る場合と比較
        if i >=j:
            dp[i] = min(dp[i],abs(h[i-j]-h[i])+dp[i-j])
        else:break
print(dp[n-1])

### FIXED CODE ###

n=int(input())
h=list(map(int,input().split()))
s1, s2 = abs(h[1]-h[0]), 0
if n==2:
    print(s1)
else:
    score = [0] + [s1] + [0] * (n - 2)
    for i in range(2,n):
        s1= abs(h[i-1]-h[i])+score[i-1]
        s2= abs(h[i-2]-h[i])+score[i-2]
        score[i] = min(s1,s2)
    print(score[n-1])
import math

N = int(input())
X = list(map(int, input().split()))
cen = sorted(X)[int(-(sorted(len(X)/2)))]
sum = 0
all = True
for a in X:
    sum = sum + a
    for c in X:
            all = False
ans = 0
for b in X:
    ans = ans + (b-cen)**2
if all == True:
    ans = 0
    print(ans)
else:
    print(ans)

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
sum = 0
all = True
for a in X:
    sum = sum + a
C = int(sum / N + 0.5)
ans = 0
for b in X:
    ans = ans + (b-C)**2
print(ans)
a = int(input())

print(a*(1+a(1+a)))

### FIXED CODE ###

a = int(input())

print( a*(1+a*(1+a)) )
oni_x, oni_speed = map(int, input().split())
chi_x, chi_speed = map(int, input().split())
time = int(input())
ans = False


if oni_speed > chi_speed:
    sa = abs(oni_x, chi_x)
    sa_speed = oni_speed - chi_speed
    if sa_speed*time >= sa:
        ans = True

if ans:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

oni_x, oni_speed = map(int, input().split())
chi_x, chi_speed = map(int, input().split())
time = int(input())
ans = False


if oni_speed > chi_speed:
    sa = abs(oni_x - chi_x)
    sa_speed = oni_speed - chi_speed
    if sa_speed*time >= sa:
        ans = True

if ans:
    print('YES')
else:
    print('NO')
import math
n,m = map(int,input().split())
s = input()
t = input()
lcm = n*m//math.gcd(n,m)
ans = [0]*lcm
for i in range(n):
    ans[i*(lcm)//n] = s[i]
for i in range(m):
    if ans[i*(lcm)//m] != t[i] and 0 != ans[i*(lcm)//m]:
        print(-1)
        exit()
print(lcm)



### FIXED CODE ###

import math
n,m = map(int,input().split())
s = input()
t = input()
lcm = n*m//math.gcd(n,m)
ans = []
s_ind = lcm//n
t_ind = lcm//m
check_ind = s_ind*t_ind//math.gcd(s_ind,t_ind)
for i in range(0,lcm,check_ind):
    if s[i//s_ind] != t[i//t_ind]:
        print(-1)
        exit()
print(lcm)
N = int(input())
s = []
for i in range(0,N):
    a = input()
    s.append(sorted(a))
t = 0
for i in range(0,N):
    for j in range(i+1,N):
        if s[i] == s[j]:
            t +=1
print(t)


### FIXED CODE ###

num = input().split()
A = int(num[0])
B = int(num[1])
s = [A+B,A-B,A*B]
print(max(s))
n, k = [int(i) for i in input().split()]
result = n % abs(n - k)
print(result)


### FIXED CODE ###

n, k = [int(i) for i in input().split()]

if n >= k:
    result = min(n % k, k - (n % k))
elif 2 * n >= k > n:
    n = abs(k - n)
    result = n
else:
    result = n

print(result)