Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

#A,B,Cを決めた後、heapqをやめて全探索、たぶんTLE

# 初期入力
import heapq
from itertools import combinations
import sys
input = sys.stdin.readline  #文字列では使わない
N,A,B,C = (int(i) for i in input().split())
l =[0]*N
for i in range(N):
    l[i] = int(input())

# A,B,Cと元の竹の長さの差（絶対値）
dif_A =[]
dif_B =[]
dif_C =[]
for n in range(1,N+1):
    for j in combinations(l,n):
        #dif変数の要素＝（求める長さー今回選んだ竹の長さ合計）*10**（合成魔法の回数)＝MPの消費量、
        #               選んだ竹、
        #               A or B or C(heapqするとABCが混ざるので区別に必要)
        #if n >=2:
        dif_A.append((abs(A-sum(j)) +10*(n-1),j,"A") )
        dif_B.append((abs(B-sum(j)) +10*(n-1),j,"B") )
        dif_C.append((abs(C-sum(j)) +10*(n-1),j,"C") )

#
mp =[]
for i in dif_A: 
    for j in dif_B:
        for k in dif_C:
            if set(i[1]).isdisjoint(set(j[1])) and \
                set(i[1]).isdisjoint(set(k[1])) and \
                set(j[1]).isdisjoint(set(k[1])):
                mp.append(i[0] +j[0] +k[0])
#mp.sort()

print(min(mp))

### FIXED CODE ###

#全探索をA,B,C一度で分けた
# RE 1   ac 19

# 初期入力
import copy
from itertools import combinations
import sys
input = sys.stdin.readline  #文字列では使わない
N,A,B,C = (int(i) for i in input().split())
l =[0]*N
for i in range(N):
    l[i] = int(input())

# A,B,Cどの竹を選ぶかcombination
mp=[]
for na in range(1,N-1):
    for ja in combinations(l,na):

        l_b =copy.copy(l)
        for i2 in ja:
            if i2 in l_b:
                l_b.remove(i2)
        for nb in range(1,N):
            for jb in combinations(l_b ,nb):

                l_c =copy.copy(l_b)
                for i3 in jb:
                    if i3 in l_c:
                        l_c.remove(i3)
                for nc in range(1,N+1):
                    for jc in combinations(l_c ,nc):
                        
                        # MPの消費量＝（求める長さー今回選んだ竹の長さ合計）+10*（合成魔法の回数)
                        AA =abs(A-sum(ja)) +10*(na-1)
                        BB =abs(B-sum(jb)) +10*(nb-1)
                        CC =abs(C-sum(jc)) +10*(nc-1)
                        mp.append(AA +BB +CC)


print(min(mp))
### BUGGY CODE ###

n = int(input())
import sys
an = list(map(int, sys.stdin.readline().split()))

for i in range(n):
    for j in range(i+1, n):
        if an[i] == an[j]:
            print('NO')
            exit(0)
print('YES')

### FIXED CODE ###

n = int(input())
import sys
an = list(map(int, sys.stdin.readline().split()))

if len(set(an))==n:
    print('YES')
    exit(0)

print('NO')
### BUGGY CODE ###

from collections import deque

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

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def find(s, t):
    global g
    queue = deque()
    queue.append((0, s))
    queue.append((1, t))
    visited = ([0] * n, [0] * n)
    visited[0][s] = 1
    visited[1][t] = 1

    while queue:
        st, i = queue.popleft()
        if visited[not st][i]:
            return True
        for f in g[i]:
            if not visited[st][f]:
                visited[st][f] = 1
                queue.append((st, f))
    return False


q = int(input())
while q:
    s, t = map(int, input().split())
    print('yes' if find(s, t) else 'no')
    q -= 1

### FIXED CODE ###

n, m = map(int, input().split())
g = [set() for _ in range(n)]
group_ids = [0] * n

while m:
    s, t = map(int, input().split())
    g[s].add(t)
    g[t].add(s)
    m -= 1


def search(s, gid):
    global g, group_ids
    queue = set(g[s])
    group_ids[s] = gid

    while queue:
        i = queue.pop()
        if not group_ids[i]:
            group_ids[i] = gid
            queue.update(g[i])


gid = 1
for i in range(n):
    if group_ids[i]:
        continue
    search(i, gid)
    gid += 1

q = int(input())
while q:
    s, t = map(int, input().split())
    gs, gt = group_ids[s], group_ids[t]
    print('yes' if gs and gt and gs == gt else 'no')
    q -= 1
### BUGGY CODE ###

N,Q = map(int,input().split())
AB = [[x for x in map(int,input().split())] for _ in range(N-1)]
PX = [[x for x in map(int,input().split())] for _ in range(Q)]
 
G = [[] for _ in range(N+1)]
for a,b in AB:
    G[a].append(b)
    G[b].append(a)
 
cnt = [0]*N
for p,x in PX:
    cnt[p-1] += x

color = ["WHITE"] * (N+1)
stack = []

def dfs(u):
    stack.append(u)
    color[u] = "GRAY"

    while len(stack) > 0:
        u = stack[-1]
        if len(G[u]) == 0:
            color[u] = "BLACK"
            stack.pop()
        else:
            u_next = G[u].pop(0)
            if color[u_next] == "WHITE":
                color[u_next] = "GRAY"
                cnt[u_next-1] += cnt[u-1]
                stack.append(u_next)
dfs(1)
print(*cnt)

### FIXED CODE ###

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

N,Q = map(int,input().split())
AB = [[int(x) for x in input().split()] for _ in range(N-1)]
PX = [[int(x) for x in input().split()] for _ in range(Q)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

value = [0] * (N+1)
for p,x in PX:
    value[p] += x

def dfs(v,parent,add):
    value[v] += add
    for x in graph[v]:
        if x == parent:
            continue
        dfs(x,v,value[v])

dfs(1,0,0)

answer = ' '.join(map(str,value[1:]))
print(answer)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
n,w=map(int,input().split())
cos=[0]*(w+1)
for i in range(n):
 w1,v1=map(int,input().split())
 for j in range(w,w1-1,-1):
  f=cos[j-w1]+v1
  if(cos[j]<f):
   cos[j]=f
print(cos[-1])

  


### FIXED CODE ###

import sys
input=sys.stdin.readline
def fun(n,w):
 cos=[0]*(w+1)
 for i in range(n):
  w1,v1=map(int,input().split())
  for j in range(w,w1-1,-1):
   f=cos[j-w1]+v1
   if(cos[j]<f):
    cos[j]=f
 print(cos[-1])
n,w=map(int,input().split())
fun(n,w)
### BUGGY CODE ###

import bisect
 
N, M = map(int, input().split(" "))
As = [0]+list(map(int, input().split(" ")))
As.sort()
cnt = 0
cnt2 = 1
for j in range(M):
  i = As[-1-cnt]  
  i = i>>cnt2
  if j == M-1 or i < As[-1-cnt-1]:
    cnt += 1
    cnt2 = 1
    bisect.insort_left(As,i)
  else:
    cnt2 += 1
 
print(sum(As[:-cnt]))

### FIXED CODE ###

import heapq
 
N, M = map(int, input().split(" "))
As = [-i for i in map(int, input().split(" "))]
As.sort()
heapq.heapify(As)

for _ in range(M):
  i = - heapq.heappop(As)
  i = i >> 1
  heapq.heappush(As,-i)

print(-sum(As))
### BUGGY CODE ###

from sys import setrecursionlimit
setrecursionlimit(1<<30)
mod=pow(10,9)+7
def f(x,p):
  z[x][0]=z[x][1]=1
  for y in v[x]:
    if y!=p:
      if z[y][0]==-1:
        f(y,x)
      z[x][0]=(z[x][0]*z[y][1])%mod
      z[x][1]=(z[x][1]*(z[y][0]+z[y][1]))%mod
n=int(input())
v=[[] for _ in range(n)]
for x,y in [map(int,raw_input().split()) for _ in range(n-1)]:
  v[x-1].append(y-1)
  v[y-1].append(x-1)
z=[[-1,-1] for _ in range(n)]
f(0,-1)
print sum(z[0])%mod

### FIXED CODE ###

from sys import setrecursionlimit
setrecursionlimit(1<<30)
mod=pow(10,9)+7
def f(x,p):
  if z[x][0]==-1:
    z[x][0]=z[x][1]=1
    for y in v[x]:
      if y!=p:
        f(y,x)
      	z[x][0]=(z[x][0]*z[y][1])%mod
        z[x][1]=(z[x][1]*(z[y][0]+z[y][1]))%mod
n=int(input())
v=[[] for _ in range(n)]
for x,y in [map(int,raw_input().split()) for _ in range(n-1)]:
  v[x-1].append(y-1)
  v[y-1].append(x-1)
z=[[-1,-1] for _ in range(n)]
f(0,-1)
print sum(z[0])%mod
### BUGGY CODE ###

# 2019/04/29
# AtCoder Beginner Contest 085 - C

# Input
n, y = map(int,input().split())

cashl = [1000, 5000, 10000]
ansl = [-1, -1, -1]
eflg = False

# Search AC and make Accumed sum
for i in range(n+1):
    for j in range(n+1):
        for k in range(n+1):
            total = i * cashl[0] + j * cashl[1] + k * cashl[2]
            bcnt = i + j + k
            if bcnt > n or total > y:
                break
            if total == y and bcnt == n:
                ansl[0] = i
                ansl[1] = j
                ansl[2] = k
                eflg = True
                break
        if eflg == True:
            break
    if eflg == True:
        break

# Output
print(ansl[2], ansl[1], ansl[0])


### FIXED CODE ###

# 2019/04/29
# AtCoder Beginner Contest 085 - C

# Input
n, y = map(int,input().split())

cashl = [10000, 5000, 1000]
ansl = [-1, -1, -1]
eflg = False

# Search AC and make Accumed sum
for i in range(n+1):
    for j in range((n+1)-i):
        subt = i * cashl[0] + j * cashl[1]
        k = int((y - subt) / 1000)

        total = subt + k * cashl[2]
        bcnt = i + j + k

        if total == y and bcnt == n:
            ansl[0] = i
            ansl[1] = j
            ansl[2] = k
            eflg = True
            break

    if eflg == True:
        break

# Output
print(ansl[0], ansl[1], ansl[2])
### BUGGY CODE ###

import heapq
N = int(input())
A = list(map(int, input().split()))
heapq.heapify(A)
while True:
  m = heapq.heappop(A)
  n = heapq.heappop(A)
  if m + n > 0:
    heapq.heappush(A, m)
    heapq.heappush(A, n)
    break
  else:
    heapq.heappush(A, -m)
    heapq.heappush(A, -n)
print(sum(A))

### FIXED CODE ###

import heapq
N = int(input())
A = list(map(int, input().split()))
heapq.heapify(A)
while True:
  m = heapq.heappop(A)
  n = heapq.heappop(A)
  if m + n >= 0:
    heapq.heappush(A, m)
    heapq.heappush(A, n)
    break
  else:
    heapq.heappush(A, -m)
    heapq.heappush(A, -n)
print(sum(A))
### BUGGY CODE ###

N=int(input())
ls=[int(s) for s in input().split()]
ls2=[[i,ls[i]]for i in range(N)]
ls2=sorted(ls2,key=lambda x:-x[1])
ans=0
for a,b in ls2:
  M=2*b
  for i in range(max([0, a-M]),min([N,a+M])):
    if abs(i-a)==b+ls[i]:
      ans+=1
print(ans)

### FIXED CODE ###

N=int(input())
ls=[int(s) for s in input().split()]
dicA={}
dicB={}
for i in range(N):
  a=i+ls[i]
  if a in dicA:
    dicA[a]+=1
  else:
    dicA[a]=1
  b=i-ls[i]
  if b in dicB:
    dicB[b]+=1
  else:
    dicB[b]=1
ans=0
for a,na in dicA.items():
  if a in dicB:
    ans+=na*dicB[a]
print(ans)
### BUGGY CODE ###

def main():
    _ = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    C = list(map(int, input().split()))

    ans = 0
    for a in A:
        for b in B:
            if a >= b:
                continue
            for c in C:
                if c > b:
                    ans += 1
    print(ans)


main()


### FIXED CODE ###

import bisect


def main():
    N = int(input())
    A = sorted(list(map(int, input().split())))
    B = sorted(list(map(int, input().split())))
    C = sorted(list(map(int, input().split())))

    ans = 0
    for b in B:
        ans += bisect.bisect_left(A, b) * (N - bisect.bisect_right(C, b))
    print(ans)


main()
### BUGGY CODE ###

n = int(input())
all_number = input().split()
count = 0
for i in range(n):
  check = True
  for j in range(i):
    if(int(all_number[i]) > int(all_number[j])):
      check = False
      break
  if(check):
    count = count + 1
print(count)

### FIXED CODE ###

n = int(input())
all_number = input().split()
count = 0
lowest = int(all_number[0])
for i in range(n):
  if(int(all_number[i]) <= lowest):
    count = count + 1
    lowest = int(all_number[i])
print(count)
### BUGGY CODE ###

n = int(input())
numList = []
for i in range(n):
  numList.append(int(input()))

workList = numList[:]
for j in range(n):
  workList.remove(numList[j])
  print(max(set(workList)))
  workList = numList.copy()

### FIXED CODE ###

n = int(input())
numList  = [int(input()) for i in range(n)]
maxVal = max(numList)
workList = numList[:]
workList.remove(maxVal)
secondVal = max(workList)
for num in numList:
  if num != maxVal:
    print(maxVal)
  else:
    print(secondVal)
### BUGGY CODE ###

import sys
from heapq import heappop,heappush
input = sys.stdin.readline
n,Q = map(int,input().split())
stx = [list(map(int,input().split())) for i in range(n)]
dls = [int(input()) for i in range(Q)]
event = []
for i in range(n):
  s,t,x = stx[i]
  event.append((s-x,1,x))
  event.append((t-x,-1,x))
for i in range(Q):
  d = dls[i]
  event.append((d,2,i))
event.sort()
ans = [-1]*Q
s = set()
hq = []
for t,q,x in event:
  if q == 1:
    s.add(x)
    heappush(hq,x)
  elif q == -1:
    s.remove(x)
  elif q == 2:
    while hq and hq[0] not in s:
      heappop(hq)
    if hq:
      ans[x] = hq[0]
    else:
      ans[x] = -1
print(*ans,sep="\n")

### FIXED CODE ###

import sys
from heapq import heappop,heappush
input = sys.stdin.readline
n,Q = map(int,input().split())
stx = [list(map(int,input().split())) for i in range(n)]
dls = [int(input()) for i in range(Q)]
event = []
for i in range(n):
  s,t,x = stx[i]
  event.append((s-x,1,x))
  event.append((t-x,-1,x))
for i in range(Q):
  d = dls[i]
  event.append((d,2,i))
event.sort()
ans = [-1]*Q
s = set()
hq = []
for t,q,x in event:
  if q == 1:
    s.add(x)
    heappush(hq,x)
  elif q == -1:
    s.remove(x)
  elif q == 2:
    while hq and hq[0] not in s:
      heappop(hq)
    if hq:
      ans[x] = hq[0]
    else:
      ans[x] = -1
print(*ans,sep="\n")
### BUGGY CODE ###

# -*- coding: utf-8 -*-
s = str(input())
q = int(input())  
st = s
count = 0
for i in range(q):
  k = input().split()
  if(k[0] == '1'):
    count = (count + 1) % 2
  else:
    c = count - 2
    d = int(k[1]) 
    e = k[2]
    if(c + d != 0):
      st = e + st
    else:
      st = st + e

if(count % 2 == 1):
  st = st[::-1]
      
print(st)

### FIXED CODE ###

# -*- coding: utf-8 -*-
s = str(input())
q = int(input())  
st = s
sth = s
sth2 = ""
stm = ""
stm2 = ""
count = 0
flagh = 0
flagm = 0
for i in range(q):
  k = input().split()
  if(k[0] == '1'):
    count = (count + 1) % 2
  else:
    c = count - 2
    d = int(k[1]) 
    e = k[2]
    if(c + d != 0):
      sth = e + sth
      if(len(sth) > 5000 and flagh == 0):
        flagh = 1
        sth2 = sth
        sth = ""
    else:
      stm = stm + e
      if(len(stm) > 5000 and flagm == 0):
        flagm = 1
        stm2 = stm
        stm = ""
      

st = sth + sth2 + stm2 + stm
if(count == 1):
  st = st[::-1]
  
print(st)
### BUGGY CODE ###

K, S = map(int, input().split())
counter = 0
for x in range(K+1):
  for y in range(K+1):
    for z in range(K+1):
      if x+y+z == S:
        counter += 1
print(counter)

### FIXED CODE ###

K, S = map(int, input().split())
counter = 0
for x in range(K+1):
  for y in range(K+1):
    z = S - x - y
    if z >= 0 and z <= K:
      counter += 1
print(counter)
### BUGGY CODE ###

S = input()
intS = list(map(int, S))
n = len(S)

fl = [False]*n
l = 0
res = 0

for i in range(n-3):
    if fl[i]:
        continue
    
    x = int(S[i:i+3])
    l = 0
    cnt = 0
    for j in range(i+3, n):
        x *= 10
        x += intS[j]
        x %= 2019
        if x == 0:
            cnt += 1
            fl[l] = True
            l = j+1
    
    res += (cnt+1)*cnt//2

print(res)

### FIXED CODE ###

S = list(map(int, list(input())))
S.reverse()
a = [0]*len(S)
y = 2019
x = 1
t = 0
cnt = [0]*y
res = 0
for i in range(len(S)):
    cnt[t] += 1
    t += S[i]*x
    t %= y
    res += cnt[t]
    x = x*10%y
print(res)
### BUGGY CODE ###

def main():
    n = int(input())
    a = [int(v) for v in input().split()]
    b = [a[i] for i in range(n + 1)]
    for i in reversed(range(0, n)):
        b[i] += b[i + 1]
    result = a[n]
    d = 0
    for i in range(n):
        d = 2 * d + a[i]
        if 2 ** i - d < 0:
            print(-1)
            return
        result += min(2 ** i - d, b[i + 1]) + a[i]
    d = 2 * d + a[n]
    if 2 ** n - d < 0:
        print(-1)
        return
    print(result)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    a = [int(v) for v in input().split()]
    b = [a[i] for i in range(n + 1)]
    for i in reversed(range(0, n)):
        b[i] += b[i + 1]
    pow2 = [1 for _ in range(n + 1)]
    for i in range(1, n + 1):
        pow2[i] = 2 * pow2[i - 1]
    result = a[n]
    d = 0
    for i in range(n):
        d = 2 * d + a[i]
        if pow2[i] - d < 0:
            print(-1)
            return
        result += min(pow2[i] - d, b[i + 1]) + a[i]
    d = 2 * d + a[n]
    if pow2[n] - d < 0:
        print(-1)
        return
    print(result)


if __name__ == '__main__':
    main()
### BUGGY CODE ###

h,w=map(int,input().split())
s=[input() for _ in range(h)]
dy=[0,0,1,-1]
dx=[1,-1,0,0]
import sys
sys.setrecursionlimit(100000)
def dfs(y,x):
    global check
    global was
    was[y][x]=1
    if s[y][x]=="#":
        check[0]+=1
    else:
        check[1]+=1
    for k in range(4):
        nx=x+dx[k]
        ny=y+dy[k]
        if nx >= 0 and ny >= 0 and nx < w and ny < h and s[ny][nx] != s[y][x] and not was[ny][nx]:
            dfs(ny,nx) 
ans=0
was=[[0 for _ in range(w)] for _ in range(h)]
for i in range(w):
    for j in range(h):
        if not was[j][i]:
            check=[0,0]
            dfs(j,i)
            ans+=check[0]*check[1]
print(ans)

### FIXED CODE ###

H,W=map(int,input().split())
S=[input() for i in range(H)]
visit=[[False]*W for i in range(H)]
par=[[None]*W for i in range(H)]
dd={}
X=[-1,0,1,0]
Y=[0,-1,0,1]
for j in range(H):
    for i in range(W):
        if visit[j][i]:
            continue
        if S[j][i]=='.':
            continue
        lH=[]
        lH.append((j,i,0))#0が黒
        par[j][i]=(i,j)
        num=0
        while lH:
            y,x,t=lH.pop()
            visit[y][x]=True
            for k in range(4):
                nx=x+X[k]
                ny=y+Y[k]
                if 0<=nx<W and 0<=ny<H:
                    if visit[ny][nx]:
                        continue
                    if t==0 and S[ny][nx]=='.':
                        visit[ny][nx]=True
                        num+=1
                        lH.append((ny,nx,1))
                    elif t==1 and S[ny][nx]=='#':
                        visit[ny][nx] = True
                        par[ny][nx]=(i,j)
                        lH.append((ny,nx,0))
        dd[(i,j)]=num
ans=0
for j in range(H):
    for i in range(W):
        if S[j][i]=='#':
            x,y=par[j][i]
            ans+=dd[(x,y)]
print(ans)
### BUGGY CODE ###

N, W = map(int, input().split())
dp = [[float("inf")] * (10**5 + 1) for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
  w, v = map(int, input().split())
  for j in range(10**5 + 1):
    dp[i+1][j] = min(dp[i][j], dp[i][j-v] + w) if j >= v and dp[i][j-v] + w <= W else dp[i][j]

ans = 0
for i in range(10**5 + 1):
  if dp[-1][i] <= W:
    ans = i
print(ans)

### FIXED CODE ###

N, W = map(int, input().split())
dp = [[float("inf")] * (10**5 + 1) for i in range(N+1)]
dp[0][0] = 0

for i in range(N):
  w, v = map(int, input().split())
  for j in range(10**5 + 1):
    dp[i+1][j] = min(dp[i][j], dp[i][j-v] + w) if j >= v and dp[i][j-v] + w <= W else dp[i][j]

ans = 0
for i in range(10**5 + 1):
  if dp[-1][i] <= W:
    ans = i
print(ans)
### BUGGY CODE ###

def Triangles(N, Lrand):
    L = sorted(Lrand, reverse=True)
    cnt = 0
    for i in range(N):
        for j in range(i+1, N):
            if L[i] >= L[j] * 2: break
            for k in range(j+1, N):
                if L[i] >= L[j] + L[k]: break
                cnt += 1
    return cnt

N = int(input())
L = [int(x) for x in input().split()]
print(Triangles(N, L))

### FIXED CODE ###

from bisect import bisect_left

def Triangles(N, L):
    asc = sorted(L)
    cnt = 0
    for i in range(N-2):
        l1 = asc[i]
        for j in range(i+1, N-1):
            l2 = asc[j]
            pos = bisect_left(asc, l1+l2)
            cnt += pos - 1 - j
    return cnt

N = int(input())
L = list(map(int, input().split()))
print(Triangles(N, L))
### BUGGY CODE ###

S=input()
ans=0
for i in range(len(S)):
    if S[i]=="A":
        for j in range(i+1,len(S)):
            if S[j]=="Z":
                ans=max(ans,j-i+1)
print(ans)

### FIXED CODE ###

S=input()
start=0
end=len(S)+1
for s in S:
    start+=1
    if s=="A":
        break
for s in S[::-1]:
    end-=1
    if s=="Z":
        break
print(end-start+1)
### BUGGY CODE ###

a = int(input())
ar = [int(input()) for i in range(a)]
for i in range(a):
    b = ar[i]
    del ar[i]
    print(max(ar))
    ar.insert(i,b)

### FIXED CODE ###

a = int(input())
ar = [int(input()) for i in range(a)]
br = sorted(ar)
am = max(ar)
bm = br[-2]
for r in ar:
    if r == am:
        print(bm)
    else:
        print(am)
### BUGGY CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    ans = []
    for i in range(T):
        N = next(it)

        val = 0; a1 = []; a2 = []
        for i, v1, v2 in ((next(it), next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            a, v, diff = (a1, v2, diff) if diff >= 0 else (a2, v1, -diff)
            a.append((diff, i))
            val += v
        a1.sort(reverse=True); a2.sort(reverse=True)

        ls = len(a1)
        vis = [None]*N
        for diff, i in a1:
            j = min(i, ls) - 1
            v2 = [[-1]]
            while j >= 0:
                v1 = vis[j]
                if v1 == None:
                    val += diff
                    v2[0][0] = j-1
                    vis[j] = v2
                    break
                j, v1[0] = v1[0][0], v2[0]


        for diff, i in a2:
            j, v2 = max(i, ls), [[-1]]
            while j < N:
                v1 = vis[j]
                if not v1:
                    val += diff
                    v2[0][0] = j + 1
                    vis[j] = v2
                    break
                j, v1[0] = v1[0][0], v2[0]

        ans.append(val)

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



if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

import sys
iim = lambda: map(int, sys.stdin.readline().rstrip().split())
sys.setrecursionlimit(1000000000)

def resolve():
    it = map(int, sys.stdin.read().split())

    T = next(it)
    ans = []
    for i in range(T):
        N = next(it)

        val = 0; a1 = []; a2 = []
        for i, v1, v2 in ((next(it), next(it), next(it)) for i in range(N)):
            diff = v1 - v2
            a, v, diff = (a1, v2, diff) if diff >= 0 else (a2, v1, -diff)
            a.append((diff, i))
            val += v
        a1.sort(reverse=True); a2.sort(reverse=True)

        ls = len(a1)
        vis = [None]*(N+1)
        def root(x):
            if vis[x] == None: return x

            vis[x] = root(vis[x])
            return vis[x]
        def root(x):
            a = []
            while True:
                y = vis[x]
                if y == None:
                    break
                a.append(x)
                x = y
            for i in a:
                vis[i] = x
            return x

        for diff, i in a1:
            j = min(i, ls) - 1
            k = root(j)
            #print(diff, i, j, k,  vis)
            if k < 0: continue
            val += diff
            vis[k] = k - 1


        for diff, i in a2:
            j, v2 = max(i, ls), [[-1]]
            k = root(j)
            #print(diff, i, j, k,  vis)
            if k >= N: continue
            val += diff
            vis[k] = k + 1

        ans.append(val)

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



if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

import numpy as np
n=int(input())
a=np.array(list(map(int,input().split())))

ans=0
mod=10**9+7
for i in range(60):
    x=0
    for j in range(n):
        if (a[j] >>i&1) :x+=1

    now = x*(n-x)

    for j in range(i):
        now = now*2
    ans += now
    ans %= mod

print(ans)

### FIXED CODE ###

# import numpy as np
n=int(input())
# a=np.array(list(map(int,input().split())))
a=list(map(int,input().split()))

ans=0
mod=10**9+7
for i in range(60):
    x=0
    for j in range(n):
        if (a[j] >>i&1) :x+=1

    now = x*(n-x) % mod

    for j in range(i):
        now = now*2 % mod
    ans += now
    ans %= mod

print(ans)
### BUGGY CODE ###

import math
k = int(input())
ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        for c in range(1, k+1):
            ans += math.gcd(a, math.gcd(b, c))
print(ans)

### FIXED CODE ###

import math

k = int(input())

ans = 0
for a in range(1, k+1):
    for b in range(1, k+1):
        tmp = math.gcd(a, b)
        for c in range(1, k+1):
            ans += math.gcd(tmp, c)
print(ans)