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

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**9, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
dp[0, vws[0][1]:] = vws[0][0]
for i in range(1, n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    mask = (weights <= L)     
    return np.amax(dp_[L - weights[mask]] + values[mask])

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))


### FIXED CODE ###

import sys
import numpy as np
from numba import njit

input = sys.stdin.buffer.readline

N = int(input())
vws = [tuple(map(int, input().split())) for _ in range(N)]

n = min(2**11, N)
vws_arr = np.array(vws, np.int32)

dp = np.zeros((n, 10**5+1), np.int32)
for i in range(n):
    v, w = vws[i]
    dp[i] = dp[(i-1)//2]
    dp[i, w:] = np.maximum(dp[(i-1)//2, :-w]+v, dp[i, w:])


@njit("i4(i4[::1], i4[::1], i4, i4[::1])", cache = True)
def func(vs, ws, L, dp_):
    values = np.zeros(1 << len(vs), np.int32)
    weights = np.zeros(1 << len(vs), np.int32)
    for i in range(len(vs)):
        for bits in range(1 << len(vs)):
            if bits & (1 << i):
                values[bits] += vs[i]
                weights[bits] += ws[i]
    ret = 0
    for v, w in zip(values, weights):
        if w <= L:
            ret = max(dp_[L - w] + v, ret)
    return ret

Q = int(input())
for _ in range(Q):
    V, L = map(int, input().split())
    V -= 1
    if V < n:
        print(dp[V, L])
    else:
        Vs = []
        while V >= n:
            Vs.append(V)
            V = (V-1) // 2
        vs = vws_arr[Vs, 0]
        ws = vws_arr[Vs, 1]
        print(func(vs, ws, L, dp[V]))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10**9)
n,m=map(int,input().split())

g=[[] for i in range(n)]
for i in range(m):
  v1,v2=map(int,input().split())
  v1-=1;v2-=1
  g[v1].append(v2)

def dfs(i):
  temp=0
  for nv in g[i]:
    temp=max(temp,dfs(nv)+1)
    
  return temp  
    
res=0
for i in range(n):
  res=max(res,dfs(i))
print(res)
  
  

### FIXED CODE ###

import sys

sys.setrecursionlimit(10**9)
n,m=map(int,input().split())

g=[[] for i in range(n)]
for i in range(m):
  v1,v2=map(int,input().split())
  v1-=1;v2-=1
  g[v1].append(v2)

dp=[-1]*n  
  
def dfs(i):
  if dp[i]!=-1:
    return dp[i]
  temp=0
  for nv in g[i]:
    temp=max(temp,dfs(nv)+1)
  dp[i]=temp  
  return temp  
    
res=0
for i in range(n):
  res=max(res,dfs(i))
print(res)
### BUGGY CODE ###

s=list(input())
s=s[::-1]
l=len(s)
mod=2019
count=[0]*2019
count[0]=1
num=0
sisu=0
for i in range(l):
    num+=int(s[i])*(10**(sisu))
    num=num%mod
    count[num]+=1
    sisu+=1
ans=0
for i in range(2019):
    N=count[i]
    ans+=N*(N-1)//2
print(ans)

### FIXED CODE ###

s=list(input())
s=s[::-1]
l=len(s)
mod=2019
count=[0]*2019
count[0]=1
num=0
seki=1
for i in range(l):
    num+=int(s[i])*seki
    num=num%mod
    count[num]+=1
    seki=(seki*10)%mod
ans=0
for i in range(2019):
    N=count[i]
    ans+=N*(N-1)//2
print(ans)
### BUGGY CODE ###

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

N, M = map(int, input().split())
B = set(map(int, input().split()))
power = 1
for b in B:
    power = lcm(power, b//2)

mn = min(B)

mn2 = mn // 2
p2 = power // mn2

if p2 % 2 == 0:
    print(0)
    exit()
ans1 = M // mn2 // p2
ans2 = M // mn2 // (p2*2)
print(ans1-ans2)


### FIXED CODE ###

from fractions import gcd
def lcm(a, b):
    return a * b // gcd(a, b)
N, M = map(int, input().split())
B = set(map(lambda x: int(x)//2, input().split()))
power = 1
for b in B:
    power = lcm(power, b)

mn = min(B)
p2 = power // mn

if p2 % 2 == 0:
    print(0)
    exit()
ans1 = M // mn // p2
ans2 = M // mn // (p2 * 2)
print(ans1-ans2)
### BUGGY CODE ###

import sys
import heapq

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


def main():
    N, M = map(int, input().split())
    A = list(map(int, input().split()))

    H = []

    for a in A:
        heapq.heappush(H, -a)

    for i in range(M):
        b, c = map(int, input().split())
        for j in range(b):
            heapq.heappush(H, -c)

    ans = 0
    for i in range(N):
        ans -= heapq.heappop(H)

    print(ans)



if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys

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


def main():
    N, M = map(int, input().split())
    A = []
    for i in list(map(int, input().split())):
        A.append((i, 1))
    for i in range(M):
        b, c = map(int, input().split())
        A.append((c, b))

    A = sorted(A)
    # print(A)
    cnt = 1
    ans = 0
    while cnt <= N:
        b, c = A.pop()
        ans += b
        if c > 1:
            c -= 1
            A.append((b, c))
        cnt += 1
    print(ans)


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

N=int(input())
L=list(map(int,input().split()))
L_i=[i+1 for i in range(len(L))]

cnt=0
for i in range(N):
    P_L= [m+L[i] for m in L[i:]]
    P_L_i = [x for x in range(N-i)]
    cnt = cnt + sum([w==z for (w, z) in zip(P_L,P_L_i)])
    
print(cnt)

### FIXED CODE ###

def main():
    N=int(input())
    L=list(map(int,input().split()))
    L_i,L_j=[],[]
    L_memo = [0]*N
    cnt=0
    for i, j in enumerate(L):
        if i+j<N:
            L_memo[i+j]+=1
        if i-j>0:
            cnt+=L_memo[i-j]        
    print(cnt)
main()
### BUGGY CODE ###

s = int(input())
 
ans=0
 
def f(n):
  if (n % 2 == 0):
    return n / 2
  else:
    return 3*n + 1
  
while (True):
  a_n = [s]
  for i in range(len(a_n)):
    if (a_n.count(4) != 2):
      a_i = f(a_n.pop(-1))
      a_n.append(a_i)
    else:
      index = a_n.index(4)
      ans = a_n[index+3]
      break
    
print(ans)

### FIXED CODE ###

s = int(input())
 
ans = 0
 
if (s == 1 or s == 2 or s == 4):
  print(4)
else:
  while (s != 4):
    if (s % 2 == 0):
      s  =  int(s/2)
    else:
      s = 3*s + 1
    ans += 1
  
 
  print(ans+4)
### BUGGY CODE ###

ans = 0


def solve():

    N = int(input())
    S = input()

    def dfs(len, a, b):
        global ans

        if len == 1:
            for i in range(a, N-1):
                if S[a] != S[i]:
                    dfs(2, a, i)
        elif len == 2:
            for i in range(b, N):
                if S[b] != S[i] and S[a] != S[i]:
                    if i - b != b - a:
                        ans += 1

    for i in range(0, N-2):
        dfs(1, i, 0)

    print(ans)


if __name__ == "__main__":
    solve()


### FIXED CODE ###



def solve():

    N = int(input())
    S = input()

    r = S.count('R')
    g = S.count('G')
    b = S.count('B')

    ans = r*g*b

    for i in range(N-2):
        for j in range(i+1, N-1):
            # j - i = k - j
            k = j-i+j
            if k >= N:
                continue
            if S[i] != S[j] and S[j] != S[k] and S[k] != S[i]:
                ans -= 1

    print(ans)


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

n = int(input())
A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))
A_list = sorted(A_list)
B_list = sorted(B_list)
C_list = sorted(C_list)
cnt = 0

def is_ok(arg):
    return B_list[arg] > A_list[i]

def bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

def is_ok2(arg):
    return C_list[arg] > B_list[j]

def bisect2(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok2(mid):
            ok = mid
        else:
            ng = mid
    return ok

for i in range(n): #Aを決定
    #Aより大きいBを探す
    B_key = bisect(-1, len(B_list)-1)
    if A_list[i] < B_list[B_key]:
        for j in range(B_key, n):
            #Bより大きいCを探す
            C_key = bisect2(-1, len(C_list)-1)
            if B_list[j] < C_list[C_key]:
                cnt += n-C_key

print(cnt)


### FIXED CODE ###

n = int(input())
A_list = list(map(int, input().split()))
B_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))
A_list = sorted(A_list)
B_list = sorted(B_list)
C_list = sorted(C_list)
cnt = 0

def is_ok(arg): #　B　より小さい最大の　A
    return A_list[arg] < B_list[i]

def bisect(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok(mid):
            ok = mid
        else:
            ng = mid
    return ok

def is_ok2(arg): #　B　より大きい最小の　A
    return C_list[arg] > B_list[i]

def bisect2(ng, ok):
    while (abs(ok - ng) > 1):
        mid = (ok + ng) // 2
        if is_ok2(mid):
            ok = mid
        else:
            ng = mid
    return ok

for i in range(n): #Bを固定
    #Bより小さいAを探す
    A_key = bisect(len(A_list), 0)
    if A_list[A_key] < B_list[i]:
        #Bより大きいCを探す
        C_key = bisect2(-1, len(C_list)-1)
        if B_list[i] < C_list[C_key]:
            #print(A_key, i, C_key, A_list[A_key], B_list[i], C_list[C_key])
            cnt += (n-C_key)*(A_key+1)

print(cnt)
### BUGGY CODE ###

S = input()
if len(S) < 4:
    print(0)
    exit(0)

U = set([0])
s = int(S[-1])
U.add(s)
ans = 0
for k in range(len(S)-2,-1,-1):
    s = int(S[k])*(10**(len(S)-k-1)) + s
    s %= 2019
    if s in U:
        ans += 1
    U.add(s)
print(ans)


### FIXED CODE ###

S = input()
if len(S) < 4:
    print(0)
    exit(0)
dp = [0]*2019
dp[0] = 1
s = int(S[-1])
dp[s] = 1
ans = 0
for k in range(len(S)-2,-1,-1):
    s = int(S[k])*(pow(10,len(S)-k-1,2019)) + s
    s %= 2019
    dp[s] += 1
for e in dp:
    ans += e*(e-1)//2
print(ans)
### BUGGY CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math

Q = int(input())
q = []
for i in range(Q):
	q.append(list(map(int, input().split())))

a_list = []
b_sum = 0
a_sum = 0
a_sum_half = 0
for i in range(Q):
	if len(q[i]) == 3:
		loc = bisect.bisect(a_list, q[i][1])
		bisect.insort(a_list, q[i][1])
		length = len(a_list)
		if length % 2 == 0 and loc < length//2:
			a_sum_half += q[i][1]
		elif length % 2 == 0 and loc >= length//2:
			a_sum_half += a_list[length//2 - 1]
		elif length % 2 == 1 and loc < length // 2:
			a_sum_half += q[i][1]
			a_sum_half -= a_list[length//2]
		a_sum += q[i][1]
		b_sum += q[i][2]
	else:
		index = (length - 1)//2
		argmin_x = a_list[index]
		min_x = argmin_x*(length//2) - a_sum_half
		min_x += (a_sum - a_sum_half) - (argmin_x*(length - length//2))
		min_x += b_sum
		print("{0} {1}".format(argmin_x, min_x))

### FIXED CODE ###


import sys
from collections import deque, defaultdict
import copy
import bisect
input=sys.stdin.readline
#sys.setrecursionlimit(10 ** 9)
import math
import heapq

Q = int(input())
#Q = 100000
q = []
for i in range(Q):
	q.append(list(map(int, input().split())))
	#q.append([1, (i*17) % 10000, i])

a_list = []
a_list2 = []
b_sum = 0
a_sum = 0
a_sum_half = 0
length = 0
for i in range(Q):
	if len(q[i]) == 3:
		if len(a_list2) == 0:
			D = True
		else:
			x = heapq.heappop(a_list2)
			heapq.heappush(a_list2,x)
			D = (x <= q[i][1])
		length += 1
		if length % 2 == 0 and not D:
			a_sum_half += q[i][1]
			heapq.heappush(a_list, -q[i][1])
		elif length % 2 == 0 and D:
			heapq.heappush(a_list2, q[i][1])
			x = heapq.heappop(a_list2)
			heapq.heappush(a_list, -x)
			a_sum_half += x
		elif length % 2 == 1 and not D:
			a_sum_half += q[i][1]
			heapq.heappush(a_list, -q[i][1])
			x = heapq.heappop(a_list)
			a_sum_half += x
			heapq.heappush(a_list2, -x)
		else:
			heapq.heappush(a_list2, q[i][1])
		a_sum += q[i][1]
		b_sum += q[i][2]
	else:
		if length % 2 == 0:
			argmin_x = -heapq.heappop(a_list)
			heapq.heappush(a_list, -argmin_x)
		else:
			argmin_x = heapq.heappop(a_list2)
			heapq.heappush(a_list2, argmin_x)
		min_x = argmin_x*(length//2) - a_sum_half
		min_x += (a_sum - a_sum_half) - (argmin_x*(length - length//2))
		min_x += b_sum
		print("{0} {1}".format(argmin_x, min_x))
### BUGGY CODE ###

import numpy as np
N, Q = map(int, input().split())

S = input()
AC_place_arr = np.zeros(N)
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        AC_place_arr[i] = 1


outputs = []
for i in range(Q):
    l, r = map(int, input().split())
    count = int(np.sum(AC_place_arr[l-1:r-1]))
    outputs.append(count)

for i in outputs:
    print(i)


### FIXED CODE ###


N, Q = map(int, input().split())

S = input()
cumurative_sum_lst = [0]*(N+1)
for i in range(N-1):
    if S[i] == "A" and S[i+1] == "C":
        cumurative_sum_lst[i+1] = cumurative_sum_lst[i] + 1
    else:
        cumurative_sum_lst[i+1] = cumurative_sum_lst[i]

outputs = []
for i in range(Q):
    l, r = map(int, input().split())
    l, r = l - 1, r - 1

    tmp = cumurative_sum_lst[r] - cumurative_sum_lst[l]
    outputs.append(int(tmp))

for i in outputs:
    print(i)
### BUGGY CODE ###

n = int(input())
s = input()

dp = [[[0 for _ in range(1000)] for _ in range(4)] for _ in range(n+1)]
dp[0][0][0] = 1
ans = 0

for i in range(n):
    for j in range(4):
        for k in range(1000):
            if dp[i][j][k] == 0: continue
            dp[i+1][j][k] = 1
            if j <= 2:
                dp[i+1][j+1][k*10 + int(s[i])] = 1

for k in range(1000):
    ans += dp[n][3][k]
print(ans)


### FIXED CODE ###

n = int(input())
s = input()

ones = set()
twos = set()
threes = set()

for a in s:
    for item in twos:
        threes.add(item+a)
    for item in ones:
        twos.add(item+a)
    ones.add(a)

print(len(threes))
### BUGGY CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n=int(input())
    A=list(map(int, input().split()))
    ans = 0
    mod = 10**9 + 7
    for i in range(60):
        q = sum(map(lambda x: x & 0b1,A))
        ans += q*(n-q)*pow(2, i, mod)
        ans = ans % mod
        A = list(map(lambda x: x >>1,A))
    print(ans)
 
if __name__=='__main__':
    main()

### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()
 
def main():
    n=int(input())
    A=list(map(int, input().split()))
    ans = 0
    mod = 10**9 + 7
    for i in range(60):
        q = sum(map(lambda x:((x >> i) & 0b1),A))
        ans += q*(n-q)*pow(2, i, mod)
        ans = ans % mod
    print(ans)
 
if __name__=='__main__':
    main()
### BUGGY CODE ###

N = int(input())
A = [int(x) for x in input().split()]

for i in range(N) :
    print(A.count(i+1))

### FIXED CODE ###

N = int(input())
A = [int(x) for x in input().split()]
cnt = [0 for y in range(N)]

for i in range(N-1) :
    cnt[A[i]-1] += 1

for i in range(N) :
    print(cnt[i])
### BUGGY CODE ###

import numpy as np

n = int(input())
a = np.array([int(x) for x in input().split()])
mod = 10**9+7
mod_sum = 0
for i in range(n-1):
    mod_sum += a[i] * sum(a[i+1:]) % mod

print(mod_sum%mod)


### FIXED CODE ###

import numpy as np

n = int(input())
a = np.array([int(x) for x in input().split()])
mod = 10**9+7
mod_sum = 0
a_sum = sum(a)
for i in range(n-1):
    a_sum -= a[i]
    mod_sum += (a[i] % mod) * (a_sum % mod) % mod

print(mod_sum%mod)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10**6)

N, Q = list(map(int, input().split()))
nodes = {i:[] for i in range(N)}
for i in range(N-1):
  r, e = list(map(int, input().split()))
  r, e = r - 1, e - 1
  nodes[r].append(e)
  nodes[e].append(r)
#print(nodes)

result = [0] * N
for i in range(Q):
  r, s = list(map(int, input().split()))
  result[r-1] += s

def dfs(r, prev=-1):
  for i in nodes[r]:
    if i == prev:
      continue
    result[i] += result[r]
    dfs(i, r)

dfs(0)
print(" ".join(map(str, result)))


### FIXED CODE ###

#人の（ほぼ同じなのにうまくいかないので）
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**6)

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

def dfs(v, parent):
    for u in lines[v]:
        if u != parent:
            ans[u] += ans[v]
            dfs(u, v)

dfs(0, -1)
print (*ans)
### BUGGY CODE ###

from collections import deque


def read():
    H, W = list(map(int, input().split()))
    S = list()
    S.append(['#'] * (W+2))
    for h in range(H):
        s = list('#' + input() + '#')
        S.append(s)
    S.append(['#'] * (W+2))
    return H, W, S


def bfs(y, x, H, W, S):
    visited = [[False for j in range(W+2)] for i in range(H+2)]
    q = deque()
    q.appendleft((y, x, 0))
    max_depth = 0
    while len(q) > 0:
        y, x, depth = q.pop()
        visited[y][x] = True
        max_depth = max(max_depth, depth)
        for dy, dx in [(0,1), (1,0), (0,-1), (-1,0)]:
            ny, nx = y+dy, x+dx
            if S[ny][nx] == '.' and not visited[ny][nx]:
                q.appendleft((ny, nx, depth+1))
    return max_depth


def reset_depth(H, W, depth, S, INF=10**7):
    for i in range(H+2):
        for j in range(W+2):
            if S[i][j] == '#':
                depth[i][j] = -2
            else:
                depth[i][j] = -1


def solve(H, W, S):
    dist_max = 0
    for i in range(1, H+1):
        for j in range(1, W+1):
            if S[i][j] == '.':
                d = bfs(i, j, H, W, S)
                dist_max = max(d, dist_max)
    return dist_max


if __name__ == '__main__':
    inputs = read()
    print("{}".format(solve(*inputs)))


### FIXED CODE ###

from collections import deque


def bfs(y, x, H, W, S):
    dirs = [(-1, 0), (0, -1), (1, 0), (0, 1)]
    depth = [[-1] * (W+2) for h in range(H+2)]
    q = deque()
    q.append((y, x))
    depth[y][x] = 0
    max_depth = 0
    while q:
        y, x = q.popleft()
        max_depth = max(max_depth, depth[y][x])
        for dy, dx in dirs:
            ny, nx = y + dy, x + dx
            if S[ny][nx] == '.' and depth[ny][nx] == -1:
                depth[ny][nx] = depth[y][x] + 1
                q.append((ny, nx))
    return max_depth


def solve():
    H, W = map(int, input().split())
    S = list()
    S.append(['#'] * (W+2))
    for _ in range(H):
        buf = input()
        S.append(list('#' + buf + '#'))
    S.append(['#'] * (W+2))

    dist_max = 0
    for y in range(H):
        for x in range(W):
            if S[y+1][x+1] == '.':
                d = bfs(y+1, x+1, H, W, S)
                dist_max = max(d, dist_max)
    print(dist_max)


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

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

dp=[float('inf')]*n
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(2,n):
    for j in range(max(i-k,0),i):
        dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[-1])

### FIXED CODE ###

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

dp=[float('inf')]*n
dp[0]=0
dp[1]=abs(h[1]-h[0])
for i in range(2,n):
    for j in range(max(i-k,0),i):
        dp[i]=min(dp[i],dp[j]+abs(h[i]-h[j]))
print(dp[-1])
### BUGGY CODE ###

import numpy as np
 
N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
 
member = np.ones(N) * K
 
for a in A:
    member -= 1
    member[a - 1] += 1
 
res = np.array(['No', 'Yes'])[(member > 0).astype('int')]
 
for r in res:
    print(r)

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]

member = [K - Q] * N

for a in A:
    member[a - 1] += 1

for m in member:
    if m > 0: print("Yes")
    else: print("No")
### BUGGY CODE ###

n = int(input())
array = [int(i) for i in input().split()]
ans=-1e14

for i in range(n, 2*n+1):
    l_array = sorted(array[:i]) 
    r_array = sorted(array[i:])
    ans = max(ans, sum(l_array[i-n:])-sum(r_array[:n]))

print(ans)

### FIXED CODE ###

import heapq

n = int(input())
array = [int(i) for i in input().split()]
ans=-1e14
l_array = []
r_array = []
l_sum = [0]*(n+1)
r_sum = [0]*(n+1)

# left-n and right-n numbers
for i in range(n):
    heapq.heappush(l_array, array[i])
    heapq.heappush(r_array, (-array[3*n-1-i], array[3*n-1-i]))

l_sum[0] = sum(l_array)
r_sum[n] = sum([i[1] for i in r_array])

for i in range(n, 2*n):
    heapq.heappush(l_array, array[i])
    heapq.heappush(r_array, (-array[3*n-1-i], array[3*n-1-i]))
    l_min = heapq.heappop(l_array)
    r_max = heapq.heappop(r_array)[1]

    # l_sum[i-n+1] = sum(l_array)
    # r_sum[2*n-1-i] = sum([j[1] for j in r_array])
    l_sum[i-n+1] = l_sum[i-n] - l_min + array[i]
    r_sum[2*n-1-i] = r_sum[2*n-i] - r_max + array[3*n-1-i]

for i in range(n+1):
    ans = max(ans, l_sum[i]-r_sum[i])

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

import numpy as np
N , K ,Q = map(int, input().split())
s = sorted([int(input())-1 for _ in range(Q)])
initializer_list = np.full(N,K)
for i in s:
    tmp = initializer_list[i]
    initializer_list -=1
    initializer_list[i] = tmp

for i in initializer_list:
    if i > 0:
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

import numpy as np
N , K ,Q = map(int, input().split())
initializer_list = [0] * N
for _ in range(Q):
    i = int(input())-1
    initializer_list[i] += 1
    

[print('Yes') if (Q - initializer_list[i] < K) else print('No')  for i in range(N)]
### BUGGY CODE ###

# https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

N = int(input())
S = input()

ans = 0
pattern = []
for x in range(N):
    for y in range(x + 1, N):
        if (S[x] + S[y]) not in pattern:
            ans += len(set(S[y + 1:]))
            pattern.append(S[x] + S[y])

print(ans)

### FIXED CODE ###

# https://atcoder.jp/contests/sumitrust2019/tasks/sumitb2019_d

N = int(input())
S = input()
#
# ans = 0
# pattern = []
# for x in range(N):
#     for y in range(x + 1, N):
#         if (S[x] + S[y]) not in pattern:
#             ans += len(set(S[y + 1:]))
#             pattern.append(S[x] + S[y])
#
# print(ans)
ans = 0
for i in range(1000):
    key = str(i).zfill(3)
    first = S.find(key[0])
    if first == -1 or first == N:
        continue
    second = S[first + 1:].find(key[1])
    if second == -1 or (first + second + 2) == N:
        continue
    third = S[first + second + 2:].find(key[2])
    if not third == -1:
        # print(first, first + second + 1, first + second + third + 2, key)
        ans += 1
print(ans)
### BUGGY CODE ###

n = int(input())

s = list(map(str, input().split()))


lis = []
for i in range(n):
    lis.append(s[i])
    lis = lis[::-1]

print(' '.join(lis))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
print(*A[::-2],*A[N%2::2])
### BUGGY CODE ###

# -*- condig:utf-8 -*-

import sys
import collections

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

counter = collections.defaultdict(int)
o = collections.defaultdict(int)
g = collections.defaultdict(list)

for i in range(n-1):
  a,b= map(int, input().split())
  g[a].append(b)
  g[b].append(a)

for i in range(q):
  p,x= map(int, input().split())
  o[p] += x


queue = [1]
parents = []
while queue:
  p = queue.pop(0)
  parents.append(p)
  count = o[p]
  for i in g[p]:
    if not i in parents:
      queue.append(i)
    else:
      count += counter[i]
  counter[p] += count
 
for i in range(1, n+1):
  print(counter[i], end=' ')

 
  


### FIXED CODE ###


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

ct = [0] * (n+1)
o = [0] * (n+1)
g = [[] for _ in range(n+1)]

for i in range(n-1):
  a,b= map(int, input().split())
  g[a].append(b)
  g[b].append(a)

for i in range(q):
  p,x= map(int, input().split())
  o[p] += x

todo = [1]
seen = [False] * (n+1)
while todo:
  p = todo.pop(-1)
  ct[p] += o[p]
  seen[p] = True
  for i in g[p]:
    if seen[i]:
      ct[p] += ct[i]
    else:
      todo.append(i)

print(*ct[1:])