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

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

for _ in range(M):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    edges[s].append(t)

def E(stop):
    dp = [-1] * N
    dp[N - 1] = 0
    for i in range(N - 1)[:: -1]:
        total = 0
        mxI = 0
        for to in edges[i]:
            total += dp[to]
            if mxI < dp[to]:
                mxI = dp[to]
        size = len(edges[i])
        if size > 1 and stop == i:
            size -= 1
            total -= mxI
        dp[i] = total / size + 1
    return dp[0]

ans = float('inf')
for s in range(N):
    ans = min(ans, E(s))

print(ans)


### FIXED CODE ###

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

for _ in range(M):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    edges[s].append(t)

def E(stop):
    dp = [-1] * N
    dp[N - 1] = 0
    for i in range(N - 1)[:: -1]:
        total = 0
        maxE = 0
        for to in edges[i]:
            total += dp[to]
            if maxE < dp[to]:
                maxE = dp[to]
        size = len(edges[i])
        if size > 1 and stop == i:
            size -= 1
            total -= maxE
        dp[i] = total / size + 1
    return dp[0]

ans = float('inf')
for s in range(N):
    ans = min(ans, E(s))

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

import heapq

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

for i in range(m):
    a,b=[int(i) for i in input().split()]
    for j in range(a):
        List.append(b)

List.sort()
#print(List)
#print(sum(List[-n:]))
print(sum(heapq.nlargest(n, List)))


### FIXED CODE ###

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

A = [int(x) for x in input().split()]
A.sort()
max = 0
BC = []
for i in range(M):
    b,c = [int(x) for x in input().split()]
    max += b
    BC.append([c,b])

BC.sort(reverse = True)
str =[]
for c,b in BC:
    str+=[c]*b
    # print(str)
    if(len(str) > N):
        break

now = 0
for i in range(len(A)):
    if(now >= max or str[now] < A[i]):
        break
    if(A[i] < str[now]):
        A[i] = str[now]
        now+=1

# print(A)
print(sum(A))
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10000000)

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

tree = [[] for _ in range(n)]
ope = [0]*n
opef=[False]*n
ret=[0]*n

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

def counter(target,num):
    global ret
    global ope
    global opef
    ret[target]+=num
    if not tree[target]:
        return
    for i in tree[target]:
        tmp=0
        if opef[i]==False:
            tmp=ope[i]
            opef[i]=True
        counter(i,num+tmp)

for _ in range(q):
    p,x=map(int,input().split())
    ope[p-1]+=x

for i in range(n):
    if opef[i]==False:
        opef[i]=True
        counter(i,ope[i])

print(*ret)

### FIXED CODE ###

n,q = map(int,input().split())
rl = [0] * n
al = [0] * n
for i in range(n-1):
    a,b = map(int,input().split())
    rl[b-1] = a -1
for j in range(q):
    p,x = map(int,input().split())
    al[p-1] += x
for k in range(1,n):
    al[k] += al[rl[k]]
print(*al)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
g = {}
for i in range(M):
  a, b = map(int, input().split())
  if a in g.keys():
    g[a].append(b)
  else:
    g[a] = [b]
  if b in g.keys():
    g[b].append(a)
  else:
    g[b] = [a]
ans = [0 for _ in range(N+1)]
#print(g)
current = [1]
while 0 in ans[2:]:
  #print(ans)
  next = []
  for i in current:
    #print('i',i)
    for j in g[i]:
      if ans[j] == 0:
        ans[j] = i
        next.append(j)
  current = next
print('Yes')
for i in range(2,N+1):
  print(ans[i])


### FIXED CODE ###

import sys
from collections import defaultdict
input = sys.stdin.readline
N, M = map(int, input().split())
g = defaultdict(list)
for i in range(M):
  a, b = map(int, input().split())
  g[a].append(b)
  g[b].append(a)
que = [1]
ans = [0 for _ in range(N+1)]
while len(que)>0:
  current = que.pop(0)
  for next in g[current]:
    if ans[next] == 0:
      que.append(next)
      ans[next] = current
print('Yes')
for i in range(2,N+1):
  print(ans[i])
### BUGGY CODE ###

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

# if min(A[0],A[-1])+k
for _ in range(k):
    finish=True
    start=[0]*n
    end=[0]*n
    
    for i in range(n):
        if A[i]!=n:
            finish=False
        start[max(0,i-A[i])]+=1
        end[min(n-1,i+A[i])]+=1
    if finish:
        break
    
    # update ans
    cnt=0
    for i in range(n):
        cnt+=start[i]
        A[i]=cnt
        cnt-=end[i]

print(*A)

### FIXED CODE ###

import sys
from itertools import accumulate
input=sys.stdin.buffer.readline

def main():
    n, k = map(int, input().split())
    A = [*map(int, input().split())]
    
    # for _ in range(min(k,int(math.log(n,2)))):
    
    for _ in "_"*k:
        b=[0]*(n)
        
        for i,v in enumerate(A):
            if i>v:
            # b[max(0,i-v)]+=1
                b[i-v]+=1
            else:
                b[0]+=1
            j=i-~v
            # if i+v+1<n:
            #     b[i+v+1]-=1
            if j<n:
                b[j]-=1
        
        # update ans
        # cnt=0
        # for i in range(1,n):
        #     b[i]+=b[i-1]
        A=[*accumulate(b)]
        
        if min(A)==n:
            break
    print(" ".join(map(str,A)))

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

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0] * n
t = []

for i in range(1,n):
    for l in range(1,k+1):
        if not i - l < 0:
            t.append(abs(h[i] - h[i-l]) + dp[i-l])
        else:
            break

    dp[i] = min(t)
    t.clear()

print(dp[-1])

### FIXED CODE ###

n,k = map(int,input().split())
h = list(map(int,input().split()))
dp = [0] * n
t = []
 
for i in range(1,n):
    for l in range(1,k+1):
        if i - l >= 0:
            t.append(abs(h[i] - h[i-l]) + dp[i-l])
        else:
            break
    dp[i] = min(t)
    t.clear()
 
print(dp[-1])
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000)

from functools import lru_cache

def resolve_by_dfs():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]
 
    @lru_cache(maxsize=None)
    def dfs(w, i):
        if i >= N:
            res = 0
        elif w < w_v[i][0]:
            res = dfs(w, i+1)
        else:
            res = max(dfs(w - w_v[i][0], i+1) + w_v[i][1], dfs(w, i+1))
        return res

    res = dfs(W, 0)
    print(res)
    
if __name__ == "__main__":
    resolve_by_dfs()

### FIXED CODE ###

def resolve():
    N, W = map(int, input().split())    
    w_v = [list(map(int, input().split())) for _ in range(N)]  # [N][0:weight, 1:value]

    dp = [[0] * (W+1) for _ in range(N+1)] 

    for i in range(N-1,-1,-1):
        for j in range(W+1):
            w = w_v[i][0]
            v = w_v[i][1]
            if j < w_v[i][0]:
                dp[i][j] = dp[i+1][j]
            else:
                dp[i][j] = max(dp[i+1][j], dp[i+1][j - w] + v)
 
    print(dp[0][W])
 
if __name__ == "__main__":
    resolve()
### BUGGY CODE ###

import sys
from itertools import product

read = sys.stdin.readline
X, Y, Z, K = map(int, read().split())
lst_A = sorted(map(int, read().split()), reverse=True)
lst_B = sorted(map(int, read().split()), reverse=True)
lst_C = sorted(map(int, read().split()), reverse=True)


lst_AB = sorted([a+b for a, b in product(lst_A, lst_B)], reverse=True)
lst_AB_K = lst_AB[:K]


lst_C_K = lst_C[:K]
lst_ABC = sorted([ab+c for ab, c in product(lst_AB_K, lst_C_K)], reverse=True)
lst_ABC_K = lst_ABC[:K]


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


### FIXED CODE ###

import sys
from itertools import product


X, Y, Z, K = map(int, input().split())
lst_A = list(map(int, input().split()))
lst_B = list(map(int, input().split()))
lst_C = list(map(int, input().split()))
lst_A.sort(reverse=True)
lst_B.sort(reverse=True)
lst_C.sort(reverse=True)

# lst_A_K = lst_A[:K]
# lst_B_K = lst_B[:K]
lst_C_K = lst_C[:K]


lst_AB = sorted([a+b for a, b in product(lst_A, lst_B)], reverse=True)
lst_AB_K = lst_AB[:K]

lst_ABC = sorted([ab+c for ab, c in product(lst_AB_K, lst_C_K)], reverse=True)
lst_ABC_K = lst_ABC[:K]

print(*lst_ABC_K, sep="\n")
### BUGGY CODE ###

import numpy as np
n = int(input())
s = input()
r, g, b = [], [], []
for i in range(n):
    if s[i] == "R":
        r.append(i)
    elif s[i] == "G":
        g.append(i)
    else:
        b.append(i)
ans = len(r)*len(b)*len(g)
r, g, b = np.array(r), np.array(g), np.array(b)
for i in r:
    for j in g:
        for k in b:
            a = sorted([i,j,k])
            if a[1] - a[0] == a[2] - a[1]:
                ans -= 1

print(ans)

### FIXED CODE ###

n = int(input())
s = input()
r, g, b = set(), set(), set()
for i in range(n):
    if s[i] == "R":
        r.add(i)
    elif s[i] == "G":
        g.add(i)
    else:
        b.add(i)

ans = len(r)*len(b)*len(g)
for i in r:
    for j in g:
        chk = j - i
        if chk + j in b:
            ans -= 1
        if i - chk in b:
            ans -= 1
        if (i + j)/2  in b:
            ans -= 1

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

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

def num_sum(n: int, a: list, dp: list, mod):
    dp[0][0] = 1
    nodes = [(0,0)]
    for i in range(n):
        next_nodes = set()
        for r,sm in nodes:
            next_nodes.add((r,sm))
            next_nodes.add((r+1, sm+a[i]))
            
            dp[r+1][sm+a[i]] += dp[r][sm]
            dp[r+1][sm+a[i]] %= mod
            
        nodes = sorted(list(next_nodes), key=lambda x: x[1], reverse=True)
    return dp

def remove(n: int, a: list, dp: list, mod):
    ret = 0
    thr = sum(a)/2
    for r in range(1,n-1):
        for sm in range(sum(a)+1):
            if sm < thr:
                continue
            
            ret += dp[r][sm] * 3*((pow(2,n-r,mod) - 2)%mod)
            ret %= mod
            
    return ret

n = ni()
a = [ni() for _ in range(n)]
dp = [[0]*(sum(a)+1) for _ in range(n+1)]
mod = 998244353

dp = num_sum(n,a,dp,mod)

ans = pow(3, n, mod) - 3*pow(2, n, mod) + 3 - remove(n,a,dp,mod)

print(ans % mod)

### FIXED CODE ###

import sys
stdin = sys.stdin
 
sys.setrecursionlimit(10**5) 
 
def li(): return map(int, stdin.readline().split())
def li_(): return map(lambda x: int(x)-1, stdin.readline().split())
def lf(): return map(float, stdin.readline().split())
def ls(): return stdin.readline().split()
def ns(): return stdin.readline().rstrip()
def lc(): return list(ns())
def ni(): return int(stdin.readline())
def nf(): return float(stdin.readline())

n = ni()
a = [ni() for _ in range(n)]

suma = sum(a)
MOD = 998244353

dp_rgb = [[0]*(suma+1) for _ in range(n+1)]
dp_gb = [[0]*(suma+1) for _ in range(n+1)]

dp_rgb[0][0] = 1
dp_gb[0][0] = 1

for i, ai in enumerate(a):
    for sm in range(suma+1):
        if sm + ai <= suma:
            dp_rgb[i+1][sm+ai] += dp_rgb[i][sm] % MOD
            dp_gb[i+1][sm+ai] += dp_gb[i][sm] % MOD
            
        dp_rgb[i+1][sm] += 2 * dp_rgb[i][sm] % MOD
        dp_gb[i+1][sm] += dp_gb[i][sm] % MOD
        
ng = 3 * sum(dp_rgb[n][-(-suma//2):]) % MOD
ok = 0 if suma%2 else 3*dp_gb[n][suma//2] % MOD

print((pow(3,n,MOD) - ng + ok) % MOD)
### BUGGY CODE ###

h,w,n=map(int,input().split())
black=[tuple(map(int,input().split())) for _ in range(n)]
sblack=set(black)
ans=[0]*10
for a,b in black:
    for x in range(3):
        for y in range(3):
            cnt=0
            ok=True
            for nx,ny in [(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)]:
                dx,dy=nx-x,ny-y
                if 1<=a-dx<=h and 1<=b-dy<=w:
                    if (a-dx,b-dy) in sblack:
                        cnt+=1
                else:
                    ok=False
                    break
            if ok:
                ans[cnt]+=1
for i in range(1,10):
    ans[i]//=i
ans[0]=(h-2)*(w-2)-sum(ans[1:])
for num in ans:
    print(num)

### FIXED CODE ###

h,w,n=map(int,input().split())
black=[tuple(map(int,input().split())) for _ in range(n)]
sblack=set(black)
ans=[0]*10
for a,b in black:
    for x in range(3):
        for y in range(3):
            cnt=0
            ok=True
            for nx,ny in [(0,0),(0,1),(0,2),(1,0),(1,1),(1,2),(2,0),(2,1),(2,2)]:
                dx,dy=nx-x,ny-y
                if 1<=a-dx<=h and 1<=b-dy<=w:
                    if (a-dx,b-dy) in sblack:
                        cnt+=1
                else:
                    ok=False
                    break
            if ok:
                ans[cnt]+=1
for i in range(1,10):
    ans[i]//=i
ans[0]=(h-2)*(w-2)-sum(ans[1:])
for num in ans:
    print(num)
### BUGGY CODE ###

N, M , K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

Used = [0]*M

total_max = 0
A_count = 0
B_count = 0

counter = 0

for i in range (0, N):
	if A[i] <= K and counter ==0:
		A_count+=1
		K-=A[i]
	else:
		counter = 1
		break

counter = 0

for i in range (0, M):
	if B[i] <= K and counter ==0:
		B_count+=1
		K-=B[i]
	else:
		counter = 1
		break

totalmax = A_count+B_count


for i in range (0, A_count):
	counter = 0
	D = K + sum(A[A_count-1-i:A_count])
	for j in range (0, M):
		zencount = A_count-i-1
		if sum(B[0:j]) <= D:
			zencount+=(j+1)
		if zencount >= totalmax:
			totalmax = zencount

print(totalmax)

### FIXED CODE ###

import bisect

N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

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

for i in range (1, M):
    B[i]+=B[i-1]

V = 0
ACount = bisect.bisect_right(A, K)
if ACount !=0:
    V = K- A[ACount-1]
else:
    V=K

AInitial = ACount

BCount = bisect.bisect_right(B, V)
final = ACount+BCount

for i in range (1, AInitial):
    V = K - A[AInitial-1-i]
    BCount = bisect.bisect_right(B, V)
    final = max(final, AInitial-i+BCount)

final = max(final, bisect.bisect_right(B,K))
print(final)
### BUGGY CODE ###

import bisect

def main():
    n = int(input())
    ll = list(map(int, input().split()))
    ll.sort()

    ans = 0
    for i in range(n-2):
        e1 = ll[i]
        for j in range(i+1, n-1):
            e2 = ll[j]
            ans += bisect.bisect_left(ll[j+1:], e1+e2)

    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

import bisect

n = int(input())
ll = list(map(int, input().split()))
ll.sort()

ans = 0
for i in range(n-2):
    e1 = ll[i]
    for j in range(i+1, n-1):
        e2 = ll[j]
        ans += bisect.bisect_left(ll[j+1:], e1+e2)

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

def s(n):
	sum = 0
	for c in str(n):
		sum += int(c)
	return sum

def isSunuke(n):

	if n >= 10:
		sn = str(n)
		length = len(sn)
		nines = 0
		for c in sn:
			if c == "9":
				nines += 1
		if nines < length / 2:
			n += 1
			return False

	for m in range(n+1, n * 2):
		if m >= 10:
			sm = str(m)
			length = len(sm)
			nines = 0
			for c in sm:
				if c == "9":
					nines += 1
			if nines < length / 2:
				continue

		if (n / s(n)) > (m / s(m)):
			return False

	return True

k = int(input())
found=0
n = 1
while(found < k):

	if isSunuke(n):
		print(n)
		found +=1
		#n += (n//20)
	n += 1


### FIXED CODE ###

import math
# import datetime

def s(n):
	sum = 0
	for c in str(n):
		sum += int(c)
	return sum

k = int(input())
found=0

def next_sunuke(n, s_n, s_n_div):

	global found

	if n == 1:
		return

	log_n = int(math.log(n,10))
	m = n - 10 ** int(log_n // 1.25)
	# m = n - 1

	while m >= 1:
		s_m = s(m)
		s_mplus1 = s(m + 1)

		# if (s_m < s_mplus1 or (s_n - s_m != 1 and s_n - s_m != -8)) and m > 9:
		if (s_m < s_mplus1) and m > 9:
			m -= 10 ** int(log_n // 1.25)
			continue

		# print("check: " + str(m))

		s_m_div = m / s(m)

		if s_m_div <= s_n_div:
			next_sunuke(m, s_m, s_m_div)
			if found >= k:
				return

			found += 1
			# print("{0:d}".format(m), "{0:+d}".format(n-m), "{0:d}".format(s_m), s_m_div)
			print(m)
			break
		# else:
		# 	log_m = int(math.log(m,10))
		# 	if (m + 1) / (10 ** (log_m - 1)) == 19:

		# 		print ("skip: " + str(m) + " to " + str(10 ** log_m - 1))

		# 		m = 10 ** log_m - 1
		# 		s_mplus1 = s(m+1)
		# 		continue

		m -= 10 ** int(log_n // 1.25)


# 適当な大きいスヌケ数
current_sunuke = 999999999999999
s_current_sunuke = s(current_sunuke)
s_current_sunuke_div = current_sunuke / s_current_sunuke

# start = datetime.datetime.now()
next_sunuke(current_sunuke, s_current_sunuke, s_current_sunuke_div)
if found < k:
	print(current_sunuke)
# end = datetime.datetime.now()
# print(str(end-start))

# sunukes=[]

# n = current_sunuke - 1

# while(n >= 1):
# 	s_n = n / s(n)
# 	if s_n <= current_sunuke_n:
# 		#sunukes.insert(0,n)
# 		sunukes.append(n)
# 		current_sunuke = n
# 		current_sunuke_n = s_n
# 	n -= 1

# for n in sunukes:
# 	print (n)
### BUGGY CODE ###


def __logging(visited, rest=[]):
    if rest:
        print(' visited:'+str(visited)+'\n'+
              '    rest:'+str(rest)+'\n')
    else:
        print(' visited:'+str(visited))


def dfs(graph, start):
    stack = [(start, 0)]
    visited = {}
    visited_list = []
    distance = []
    while stack:
        temp = stack.pop(0)
        label = temp[0]
        dis = temp[1]
        if label not in visited:
            tmp = graph.get(label, [])
            tmp = list(map(lambda x: (x[0], x[1] + dis), tmp))
            stack = tmp + stack
            visited[label] = dis
            visited_list.append(label)
        else:
            if dis != visited[label]:
                return False, visited_list
        #__logging(visited, stack)
    return True, visited_list

N, M = (int(i) for i in input().split())  

m_list = range(N)
graph = {}

for i in range(M):
    L, R, D = (int(i) for i in input().split())
    if L not in graph:
        graph[L] = [(R, D)]
    else:
        graph[L].append((R, D))
    if R not in graph:
        graph[R] = [(L, -1 * D)]
    else:
        graph[R].append((L, -1 * D))

flag = True
while m_list != []:
    ans, visited_list = dfs(graph, m_list[0])
    if not ans:
        flag = False
        break
    m_list = list(set(visited_list) ^ set(m_list))

if flag:
    print('Yes')
else:
    print('No')

### FIXED CODE ###



def dfs(graph, start, visited):
    if visited[start] != -99999:
        return True
    
    stack = [start]
    visited[start] = 0
    while stack:
        label = stack.pop()
        for nextnode, distance in graph[label]:
            if visited[nextnode] == -99999:
                stack.append(nextnode)
                visited[nextnode] = visited[label] + distance
            elif visited[nextnode] != visited[label] + distance:
                return False
    return True

N, M = (int(i) for i in input().split())  

graph = [[] for i in range(N+1)]

for i in range(M):
    L, R, D = (int(i) for i in input().split())
    graph[L].append((R, D))
    graph[R].append((L, -1 * D))


visited = [-99999 for i in range(N+1)]

flag = True
for i in range(1, N + 1):
    ans = dfs(graph, i, visited)
    if not ans:
        flag = False
        break

if flag:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

# [時間、変数、処理の種類]をイベントに追加。処理の種類は1：工事開始、2：工事終了、3：判定
n, q = map(int, input().split())
events = []
ans = [-1] * q
koji = set()
for _ in range(n):
    s, t, x = map(int, input().split())
    events += [[s - x - 0.3, x, 1]]
    events += [[t - x - 0.7, x, 2]]
for i in range(q):
    d = int(input())
    events += [[d, i, 3]]
events.sort()
for j, h, s in events:
    if s == 1:
        koji.add(h)
    elif s == 2:
        koji.remove(h)
    else:
        if koji:
            ans[h] = min(koji)
print(*ans, sep="\n")


### FIXED CODE ###

import sys
from bisect import *

input = sys.stdin.readline

def f(n, q):
    xst = []
    for i in range(n):
        s, t, x = map(int, input().split())
        xst.append([x, s - x, t - x])
    xst.sort()

    ds = []
    for i in range(q):
        d = int(input())
        ds.append(d)

    ans = [-1] * q
    jump = [-1] * q

    for x, s, t in xst:
        i = bisect_left(ds, s)
        fi = bisect_left(ds, t)
        while i < fi:
            if jump[i] != -1:
                i = jump[i]
            else:
                ans[i] = x
                jump[i] = fi
                i += 1

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

n, q = map(int, input().split())
f(n, q)
### BUGGY CODE ###

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

for x in range(k):
    new_a = [0]*n
    for j,l in enumerate(a):
        for i in range(-l,l+1):
            if j+i >= 0 and j+i<n:
                new_a[j+i]+=1
    a = new_a

print(" ".join([str(x) for x in a]))

### FIXED CODE ###

import math
import numpy as np

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


for _ in range(k):
    new_a = np.zeros(n+1,dtype=int)
    np.add.at(new_a, np.maximum(0,np.arange(0, n)-a), 1)
    np.add.at(new_a, np.minimum(n,np.arange(0, n)+a+1), -1)
    a = new_a.cumsum()[:-1]
    if np.all(a==n):
        break

print(" ".join([str(x) for x in a]))
### BUGGY CODE ###

import heapq
from copy import deepcopy
from sys import stdin

N = int(stdin.readline())
a = list(map(int, stdin.readline().split()))

# 前半と後半
first, second = [], []
heapq.heapify(first)
heapq.heapify(second)

first_sum, second_sum = 0, 0

for i in range(N):
    heapq.heappush(first, a[i])
    first_sum += a[i]
    heapq.heappush(second, -a[3 * N - 1 - i])
    second_sum += a[3 * N - 1 - i]


first_tmp = deepcopy(first)
second_tmp = deepcopy(second)
first_sum_tmp = first_sum
second_sum_tmp = second_sum
ans = -10 ** 15

# first側からk個を取り除き、second側からN - k個を取り除く
for k in range(N + 1):
    first = deepcopy(first_tmp)
    second = deepcopy(second_tmp)
    first_sum = first_sum_tmp
    second_sum = second_sum_tmp
    cnt = 0

    while cnt < k:
        heapq.heappush(first, a[N + cnt])
        first_sum += a[N + cnt]
        first_sum -= heapq.heappop(first)
        cnt += 1

    while cnt < N:
        heapq.heappush(second, -a[N + cnt])
        second_sum += a[N + cnt]
        second_sum -= -heapq.heappop(second)
        cnt += 1

    ans = max(ans, first_sum - second_sum)
    # print(first_sum, second_sum)

print(ans)


### FIXED CODE ###

import heapq
from sys import stdin

N = int(stdin.readline())
a = list(map(int, stdin.readline().split()))

# 前半と後半
first, second = [], []
heapq.heapify(first)
heapq.heapify(second)

first_sum, second_sum = 0, 0

for i in range(N):
    heapq.heappush(first, a[i])
    first_sum += a[i]
    heapq.heappush(second, -a[3 * N - 1 - i])
    second_sum += a[3 * N - 1 - i]

# first, secondそれぞれ0 - Nまで探索
L_sum = [first_sum]
R_sum = [second_sum]

for i in range(N, 2 * N):
    heapq.heappush(first, a[i])
    first_sum += a[i]
    first_sum -= heapq.heappop(first)
    L_sum.append(first_sum)

    heapq.heappush(second, -a[3 * N - 1 - i])
    second_sum += a[3 * N - 1 - i]
    second_sum -= - heapq.heappop(second)
    R_sum.append(second_sum)

ans = -10 ** 15

R_sum = R_sum[::-1]

for i in range(N + 1):
    ans = max(ans, L_sum[i] - R_sum[i])

# print(L_sum, R_sum)
print(ans)