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

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush
import numpy as np


def small_dp(N,k,X):
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        c = 0
        for i in range(N//X[0][0]+1):
            j = (N-i*X[0][0])//X[1][0]
            c = max(X[0][1]*i + X[1][1]*j + (N-i*X[0][0])%X[1][0], c)
        return c
    if k == 3:
        dp = np.zeros((3, N+1), dtype=int)
        M = np.arange(N+1)
        dp[0] = X[0][1]*(M//X[0][0]) + M%X[0][0]
        for i in range(1,3):
            dp[i,:X[i][0]] = dp[i-1,:X[i][0]]
            for w in range(X[i][0],N+1):
                dp[i,w] = max(dp[i-1,w], dp[i,w-X[i][0]]+X[i][1])
        N = dp[-1][N]
        return N

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    
    for C in ((A,B), (B,A)):
        *X, = filter(lambda c: int.__sub__(*c)<0, zip(*C))
        N = small_dp(N, len(X), X)
    res = N

    return str(res)

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


### FIXED CODE ###

# -*- coding: utf-8 -*-
from itertools import product
from heapq import heappop, heappush

def small_dp(N,A,B):
    *X, = filter(lambda c: int.__sub__(*c)<0, zip(A,B))
    k = len(X)
    if k == 0:
        return N
    if k == 1:
        return X[0][1]*(N//X[0][0]) + N%X[0][0]
    if k == 2:
        c = 0
        for i in range(N//X[0][0]+1):
            j = (N-i*X[0][0])//X[1][0]
            c = max(X[0][1]*i + X[1][1]*j + (N-i*X[0][0])%X[1][0], c)
        return c
    if k == 3:
        if (N//X[1][0]+1)*(N//X[0][0]+1) <= 10**6 :
            return max(X[0][1]*i + max(X[1][1]*j + X[2][1]*((N-i*X[0][0]-j*X[1][0])//X[2][0]) + ((N-i*X[0][0]-j*X[1][0])%X[2][0]) for j in range((N-i*X[0][0])//X[1][0]+1)) for i in range(N//X[0][0]+1))
        else:
            import numpy as np
            dp = np.zeros(N+1, dtype=int)
            for w in range(1,N+1):
                dp[w] = max(dp[w-X[i][0]]+X[i][1] if w>=X[i][0] else w for i in range(k))
            N = dp[-1]
            return N

def solve():
    N = int(input())
    A = list(map(int, input().split()))
    B = list(map(int, input().split()))
    res = small_dp(small_dp(N, A, B), B, A)

    return str(res)

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

N,K,Q=map(int,input().split())
A=[int(input()) for _ in range(Q)]
l = list(map(lambda x:'Yes' if K-Q+A.count(x)>0 else 'No',list(range(1,N+1))))
for i in l:
    print(i)

### FIXED CODE ###

N, K, Q = map(int, input().split())
P = [0] * N

for i in range(Q):
    P[int(input())-1] += 1
for i in range(N):
    ans = K - Q + P[i]
    if ans > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

def gcd(m,n):
  x=max(m,n)
  y=min(m,n)
  if x==0:
    return 0
  while y!=0:
    x,y=y,x%y
  return x
 
n = int(input())
a = list(map(int, input().split()))
b = [0]
 
for i in range(n):
  a[i],a[n-1]=a[n-1],a[i]
  temp = a[0]
  for j in range(n-1):
    temp=gcd(temp,a[j])
    if temp == 1:
      break
    if temp < max(b):
      break
  b.append(temp)
  a[i],a[n-1]=a[n-1],a[i]
  
print(max(b))


### FIXED CODE ###

def gcd(m,n):
  x=max(m,n)
  y=min(m,n)
  while y!=0:
    x,y=y,x%y
  return x

n = int(input())
a = list(map(int, input().split()))
b = []
l = [0]
r = [0]

for i in range(n):
  l.append(gcd(a[i],l[i]))
  r.append(gcd(a[n-1-i],r[i]))

for i in range(n):
  b.append(gcd(l[i],r[n-1-i]))
  
print(max(b))
### BUGGY CODE ###

N , K , Q = map(int , input().split())
point = [K] * N
for _ in range(Q):
    answer = int(input())
    point = list(map(lambda x : x - 1 , point))
    point[answer - 1] += 1
for i in range(N):
    if point[i] > 0:
        print("Yes")
    else:
        print("No")


### FIXED CODE ###


N , K , Q = map(int , input().split())
point = [K] * N
for _ in range(Q):
    answer = int(input())
    point[answer - 1] += 1
point = list(map(lambda x : x - Q , point))
for i in range(N):
    if point[i] > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

s = input()
t = input()
dp = [[0] * (len(t) + 1) for _ in range(len(s) + 1)]
for i in range(1, len(s) + 1):
  for j in range(1, len(t) + 1):
    k = dp[i - 1][j]
    if dp[i][j - 1] > k:
      k = dp[i][j - 1]
    if (s[i - 1] == t[j - 1]) and (dp[i - 1][j - 1] + 1 > k):
      k = dp[i - 1][j - 1] + 1
    dp[i][j] = k
result = ''
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)

### FIXED CODE ###

s = input()
t = input()
slen = len(s)
tlen = len(t)
dp = [[0 for j in range(tlen + 1)] for i in range(slen + 1)]
for i in range(slen):
  for j in range(tlen):
    if s[i] == t[j]:
      dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j] + 1)
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i + 1][j])
    dp[i + 1][j + 1] = max(dp[i + 1][j + 1], dp[i][j + 1])
result = ''
i = slen
j = tlen
while i > 0 and j > 0:
  if dp[i - 1][j] == dp[i][j]:
    i -= 1
  elif dp[i][j - 1] == dp[i][j]:
    j -= 1
  else:
    result = s[i - 1] + result
    i -= 1
    j -= 1
print(result)
### BUGGY CODE ###

N = int(input())
L = list(map(int,input().split()))
cnt = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        for h in range(j+1,N):
            if (L[i] + L[j] + L[h] - max(L[i],L[j],L[h])) > max(L[i],L[j],L[h]):
                cnt += 1
print(cnt)

### FIXED CODE ###

N = int(input())
L = list(map(int,input().split()))
L.sort()
cnt = 0
for i in range(N-2):
    for j in range(i+1,N-1):
        h_min = j
        h_max = N
        while h_max - h_min != 1:
            h_mid = (h_max + h_min) // 2
            if L[i] + L[j] > L[h_mid]:
                h_min = h_mid
            else:
                h_max = h_mid
        cnt += h_min - j
print(cnt)
### BUGGY CODE ###

all,rolls=map(int,input().split())
List=list(map(int,input().split()))

sum = 0
sumList =[]

for i in range(all - rolls + 1):
	sum = 0
	for j in range(rolls):
		sum = sum + (List[i + j] + 1) / 2
	sumList.append(sum)

sumList.sort(reverse=True)
print(sumList[0])

### FIXED CODE ###

all,rolls=map(int,input().split())
inputList=list(map(int,input().split()))

sum = 0
sumList =[]

# 初めに全期待値計算
for i in range(all):
	inputList[i] = (inputList[i] + 1) / 2

# 最初の組み合わせの期待値計算
for i in range(rolls):
	sum = sum + inputList[i]
sumList.append(sum)

# 2番目以降の期待値計算
for i in range(all - rolls):
	sum = sum + inputList[i + rolls] - inputList[i]
	sumList.append(sum)

sumList.sort(reverse=True)
print(sumList[0])
### BUGGY CODE ###

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

def factorizationC(n,p):
    numList=[]
    for i in range(2, int(p**(1/n))+1):
        if p % (i**n) == 0:
            numList.append(i)
            m = p // (i**n)
            j = 2
            while j <= m:
                if m % (j**n) == 0:
                    numList.append(j)
                    m = m // (j**n)
                    j = 2
                else:
                    j += 1
            break
    return numList

aaa=factorizationC(n,p)

ans=1
for i in range(len(aaa)):
   ans=ans*aaa[i]

print(ans)

### FIXED CODE ###

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

def factorize(n):
    fct = []  # prime factor
    b, e = 2, 0  # base, exponent
    while b * b <= n:
        while n % b == 0:
            n = n // b
            e = e + 1
        if e > 0:
            fct.append((b, e))
        b, e = b + 1, 0
    if n > 1:
        fct.append((n, 1))
    return fct

kekka=factorize(p)

ans=1
for i in range(len(kekka)):
    ans=ans* kekka[i][0] ** (kekka[i][1]//n)
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(1000000)
n,q=map(int,input().split())
G=[[]*n for i in range(n)]
P=[0]*n
V=[0]*n
R=[0]*n
for i in range(n-1):
	a,b=map(int,input().split())
	G[a-1].append(b-1)
	G[b-1].append(a-1)
for i in range(q):
	c,d=map(int,input().split())
	P[c-1]+=d

def dsf(i,p):
    V[i]=1
    R[i]+=p+P[i]
    p=0
    if G[i]!=[]:
        for j in G[i]:
            if V[j]!=1:
                dsf(j,R[i])
dsf(0,0)
print(' '.join(map(str,R)))


### FIXED CODE ###

import sys
sys.setrecursionlimit(1000000)
s=sys.stdin.readlines()
n,q=map(int,s[0].split())
G=[[]*n for i in range(n)]
P=[0]*n
V=[0]*n
R=[0]*n
for e in s[1:n]:
    a,b=map(int,e.split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
for e in s[n:]:
    c,d=map(int,e.split())
    P[c-1]+=d

def dsf(i,p):
    V[i]=1
    R[i]+=p+P[i]
    p=0
    for j in G[i]:
        if V[j]!=1:
            dsf(j,R[i])
dsf(0,0)
print(' '.join(map(str,R)))
### BUGGY CODE ###

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

score = N + 1
a = [S[:i].count('W') + S[i+1:].count('E') for i in range(N)]
print(min(a))


### FIXED CODE ###

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

w = 0
e = S[1:].count('E')
score = w + e

for i in range(1, N):
    if S[i] == 'E':
        e -= 1
    if S[i-1] == 'W':
        w += 1
    score = min(score, w + e)

print(score)
### BUGGY CODE ###

# coding: utf-8
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())


def ILI(): return list(map(int, input().split()))


def read():
    N = II()
    a = ILI()
    return (N, a)


def check_a(N, a):
    for i, _a in enumerate(a):
        if _a >= N:
            return i
    return -1


def solve(N, a):
    ans = 0
    while True:
        ret_ind = check_a(N, a)
        if ret_ind == -1:
            break
        div, mod = divmod(a[ret_ind], N)
        for i in range(N):
            if i == ret_ind:
                a[i] = mod
                continue
            a[i] += div
        ans += div

    return ans


def main():
    params = read()
    print(solve(*params))


if __name__ == "__main__":
    main()


### FIXED CODE ###

# coding: utf-8
INF = 10 ** 20
MOD = 10 ** 9 + 7


def II(): return int(input())


def ILI(): return list(map(int, input().split()))


def read():
    N = II()
    a = ILI()
    return (N, a)


def check_a(N, a):
    for _a in a:
        if _a >= N:
            return False
    return True


def solve(N, a):
    ans = 0
    while True:
        if check_a(N, a):
            break

        l_div, l_mod = [None] * N, [None] * N
        for i, _a in enumerate(a):
            l_div[i], l_mod[i] = divmod(_a, N)

        sum_div = sum(l_div)
        for i in range(N):
            a[i] = l_mod[i] + sum_div - l_div[i]

        ans += sum_div

    return ans


def main():
    params = read()
    print(solve(*params))


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

from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

N, K  = [int(x) for x in stdin.readline().rstrip().split()]
A = [0] + [int(x) for x in stdin.readline().rstrip().split()]

stack = deque([1])
nextt = A[1]

while True:
    if not nextt in stack:
        stack.append(nextt)
    else:
        stack.append(nextt)
        break
    nextt = A[nextt]

    if len(stack) > K:
        print(stack[K])
        exit()

num1 = stack.pop()
length = len(stack)
tmp = deque([])
while True:
    num2 = stack.pop()
    if num1 != num2:
        tmp.append(num2)
    else:
        tmp.append(num2)
        break

tmp = list(tmp)[::-1]

index = (K - length) % len(tmp)

print(tmp[index])
    


### FIXED CODE ###

from sys import stdin
import math
import fractions
from collections import deque
from collections import Counter
import itertools

INF = 10 ** 10

N, K  = [int(x) for x in stdin.readline().rstrip().split()]
A = [0] + [int(x) for x in stdin.readline().rstrip().split()]

stack = [1]
nextt = A[1]
visited_dict = {1: True}

while True:
    if not visited_dict.get(nextt, False):
        stack.append(nextt)
        visited_dict[nextt] = True
    else:
        stack.append(nextt)
        break
    nextt = A[nextt]

    if len(stack) > K:
        print(stack[K])
        exit()

num1 = stack.pop()
length = len(stack)
tmp = []
while True:
    num2 = stack.pop()
    if num1 != num2:
        tmp.append(num2)
    else:
        tmp.append(num2)
        break

tmp = tmp[::-1]

index = (K - length) % len(tmp)

print(tmp[index])
### BUGGY CODE ###

h,w,m = map(int, input().split())
hl = [0] * h
wl = [0] * w
dic = set()
for i in range(m):
  x,y = map(int, input().split())
  dic.add((x,y))
  hl[x-1] += 1
  wl[y-1] += 1

h_max = max(hl)
r = [i for i in range(h) if hl[i] == h_max]
w_max = max(wl)
c = [i for i in range(w) if wl[i] == w_max]

flg = 0
for rc in r:
  for cc in c:
    if (rc+1,cc+1) not in dic:
      flg = 1
      
if flg == 0:
  print(h_max + w_max - 1)
else:
  print(h_max + w_max)

### FIXED CODE ###

def main():
  h,w,m = map(int, input().split())
  hl = [0] * h
  wl = [0] * w
  dic = set()
  for i in range(m):
    x,y = map(int, input().split())
    dic.add((x,y))
    hl[x-1] += 1
    wl[y-1] += 1

  h_max = max(hl)
  r = [i for i in range(h) if hl[i] == h_max]
  w_max = max(wl)
  c = [i for i in range(w) if wl[i] == w_max]

  flg = 0
  for rc in r:
    for cc in c:
      if (rc+1,cc+1) not in dic:
        print(h_max + w_max)
        return

  print(h_max + w_max - 1)
  
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math
mod = 10 ** 9 + 7

n = int(input())
a = [int(i) for i in input().split()]
tmp = a[0]
set_v = a[0]
pairwise = True
for i in range(1, n):
    gcd = math.gcd(tmp, a[i])
    set_v = math.gcd(set_v, a[i])
    if gcd  > 1:
        pairwise = False
    tmp = (a[i] * tmp) // gcd
if pairwise == True:
    ans = 'pairwise coprime'
elif set_v == 1:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)

### FIXED CODE ###

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return set(a)

import math
mod = 10 ** 9 + 7

n = int(input())
a = [int(i) for i in input().split()]
tmp = a[0]
set_v = a[0]
pairwise = True
prime_list = set([])
for i in range(1, n):
    prime = prime_factorize(a[i])
    set_v = math.gcd(set_v, a[i])
    for p in prime:
        if p in prime_list:
            pairwise = False
        prime_list.add(p)
if pairwise == True:
    ans = 'pairwise coprime'
elif set_v == 1:
    ans = 'setwise coprime'
else:
    ans = 'not coprime'
print(ans)
### BUGGY CODE ###

N,K,C = map(int,input().split())
S = list(input())
W = [i for i in range(N) if S[i]=="o" ]
# print(W)

for w in W:
    S[w] = "x"
    i = 0
    count = 0
    while i<N and count<K:
        if S[i] == "o":
            count += 1
            i += C
        i += 1
    
    # print("w,count",w,count)
    if count < K:
        print(w+1)
    
    S[w] = "o"

### FIXED CODE ###

N,K,C = map(int,input().split())
S = list(input())
W = [i for i in range(N) if S[i]=="o" ]
# print(W)

def LR(S,f):
    D = {}
    i = 0
    count = 0
    while i<N and count<K:
        if S[i] == "o":
            count += 1
            if f:
                D[count] = i
            else:
                D[m+1-count] = N-1 - i
            i += C
        i += 1
    return D

L = LR(S,True)
m = max(L)
S.reverse()
R = LR(S,False)
# print(L,R)

for i in range(1,m+1):
    if L[i]==R[i]:
        print(L[i]+1)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
from sys import stdin

ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

N, W = ds_in()

dp = [[0] * (W+1) for i in range(N+1)]
# dp[index][weight]:=valueとしてdp[n]での最大を求める.
for i in range(N):
    # pre = values.copy()
    w, v = ds_in()  # [weight, value]
    for j in range(W+1):
        if (j-w>=0):
            dp[i+1][j] = max(dp[i][j], dp[i][j-w]+v)
        else:
            dp[i+1][j] = dp[i][j]
ans = 0
for i in range(W+1):
    ans = max(ans, dp[N][i])
print(ans)


### FIXED CODE ###

# -*- coding: utf-8 -*-
from sys import stdin

def main():
    ds_in = lambda: list(map(int, stdin.readline().split()))  # List = ds_in()

    N, W = ds_in()

    dp = [[0] * (W+1) for i in range(N+1)]
# dp[index][weight]:=valueとしてdp[n]での最大を求める.
    for i in range(N):
    # pre = values.copy()
        w, v = ds_in()  # [weight, value]
        for j in range(W+1):
            if (j-w>=0):
                dp[i+1][j] = max(dp[i][j], dp[i][j-w]+v)
            else:
                dp[i+1][j] = dp[i][j]
    ans = 0
    for i in range(W+1):
        ans = max(ans, dp[N][i])
    print(ans)
    return 0
main()
### BUGGY CODE ###

H, N = [int(i) for i in input().split()]
An = []
Bn = []
#Rn = []
for n in range(N):
  a, b = [int(i) for i in input().split()]
  An.append(a)
  Bn.append(b)
#  Rn.append(b/a)

maxA = max(An)
dp = [[1000000000 for _ in range(H+1 )] for _ in range(N+1)]
dp[0][0] = 0
for n in range(N):
  dp[n][0] = 0
  a, b = An[n], Bn[n]
  for h in range(1, H+1):
    if h == H:
      dp[n+1][h] = min(min(dp[n][h-a:]) + b, dp[n][h], 
                       min(dp[n+1][h-a:]) + b)
    elif h >= a:
      dp[n+1][h] = min(dp[n][h-a] + b, dp[n][h], dp[n+1][h-a] + b)
    else:
      dp[n+1][h] = dp[n][h]
print(dp[N][H])
    


### FIXED CODE ###

import numpy as np

H, N = map(int, input().split())
AB = np.array([list(map(int, input().split())) for i in range(N)])
A = AB[:, 0]
B = AB[:, 1]

dp = np.array([0]*(H+1))

for i in range(1, H+1):
    dp[i] = min(dp[np.maximum(i - A, 0)] + B)

print(dp[-1])
### BUGGY CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()
rt = [[] for i in range(n)]
dk = [10**10] * n
srb = [None]*n

for i in range(m):
    a,b = mi()
    rt[a-1].append(b-1)
    rt[b-1].append(a-1)

l = []
dk[0] = 0
for i in rt[0]:
    l.append(i)
    dk[i] = 1
    srb[i] = 1

while len(l) != 0:
# for j in range(20):
    # ルートが最小のnodeを見つける
    mincost = 10**6
    for i in l:
        if mincost > dk[i]:
            mincost = dk[i]
            minnode = i
    # そのnodeの数字を確定し、
    l.remove(minnode)
        
    # 隣接する確定してないnodeにコストを上書き（小さければ）
    # queueに隣接nodeをappend
    for i in rt[minnode]:
        if dk[i] > dk[minnode]:
            dk[i] = dk[minnode]+1
            srb[i] = minnode+1
            if i not in l:
                l.append(i)

    
print('Yes')
for i in range(1,n):
    print(srb[i])






### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

n,m = mi()

rt = [[] for i in range(n)]
srb = [None] * n
dk = [10**10]*n


for i in range(m):
    a,b = mi()
    rt[a-1].append(b-1)
    rt[b-1].append(a-1)

from collections import deque
l = deque()

srb[0] = 0
for i in rt[0]:
    l.append(i)
    srb[i] = 1

while len(l) != 0:
    c = l.popleft()
    for i in rt[c]:
        if srb[i] == None:
            l.append(i)
            srb[i] = c+1

print('Yes')
for i in range(1,n):
    print(srb[i])
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))

pair = n*(n - 1)/2
not_4 = 0
ans = 'Yes'
num = len(a)
for i in range(num):
  for j in range(num):
    
    if i != j and a[i]*a[j]%4 != 0:
      not_4 += 1
      
      if not_4 >= pair:
        ans = 'No'
        break
    
print(ans)

### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))

four = 0
two = 0
one = 0
for i in a:
  if i%4 == 0:
    four += 1
  elif i%2 == 0 and i%4 != 0:
    two += 1
  elif i%2 != 0:
    one += 1

if four >= one or four + 1 >= two//2 + two%2 + one or n == two:
  print('Yes')
else:
  print('No')
### BUGGY CODE ###

#atcoder template
def main():
    import sys
    imput = sys.stdin.readline
    #文字列入力の時は上記はerrorとなる。
    #ここにコード
    #input
    h, w = map(int, input().split())
    c_h, c_w = map(int, input().split())
    d_h, d_w = map(int, input().split())
    s = ["" for _ in range(h)]
    for i in range(h):
        s[i] = str(input())

    #output
    from collections import deque

    INF = pow(10, 10)
    dp = [[INF] * w for _ in range(h)]

    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]
    dxb = [-2, -2, -2, -2, -2, -1, -1, -1, -1, 0, 0, 1, 1,  1, 1, 2, 2, 2, 2, 2]
    dyb = [-2, -1, 0,   1,  2, -2, -1,  1,  2,-2, 2, -2,-1, 1, 2, -2,-1,0, 1, 2]

    def clear_maze(sx, sy, gx, gy, maze):
        def bfs():
            q = deque([])
            q.append((sx, sy))
            dp[sx][sy] = 0

            while len(q):
                x, y = q.popleft()

                if x == gx and y == gy:
                    break

                for i in range(0, 4):
                    nx, ny = x + dx[i], y + dy[i]
                    if 0 <= nx < h and 0 <= ny < w and maze[nx][ny] != "#" and dp[nx][ny] > dp[x][y]:
                        q.appendleft((nx, ny))#ここを変更
                        dp[nx][ny] = dp[x][y]#ここを変更

                for j in range(0, 20):
                    nx2, ny2 = x + dxb[j], y + dyb[j]
                    if 0 <= nx2 < h and 0 <= ny2 < w and maze[nx2][ny2] != "#" and dp[nx2][ny2] > dp[x][y]:
                        q.append((nx2, ny2))
                        dp[nx2][ny2] = dp[x][y] + 1 
            return dp[gx][gy]
        return bfs()

    answer = clear_maze(c_h-1, c_w-1, d_h-1, d_w-1, s) if clear_maze(c_h-1, c_w-1, d_h-1, d_w-1, s) < INF else "-1" 
    # %%
    print(answer)

    #N = 1のときなどcorner caseを確認！
if __name__ == "__main__":
    main()

### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
maze = [input() for _ in range(H)]

INF = 10 ** 12
path = [[INF] * W for _ in range(H)]  # path: 各マスへの移動コスト

# walk:移動A, warp:移動B
walk = [(0, 1), (0, -1), (-1, 0), (1, 0)]
warp = [(i, j) for i in range(-2, 3) for j in range(-2, 3) if (i, j) not in [(0, 0)] + walk]

q = deque()
path[Ch][Cw] = 0
q.append((Ch, Cw, 0))

while q:
    x, y, s = q.popleft()
    for dx, dy in walk:  # 移動A
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s:
            path[nx][ny] = s
            q.appendleft((nx, ny, s))  # 移動Aの場合はコスト0. キューの先頭に追加する.
    for dx, dy in warp:  # 移動B
        nx = x + dx
        ny = y + dy
        if 0 <= nx < H and 0 <= ny < W and maze[nx][ny] == '.' and path[nx][ny] > s + 1:
            path[nx][ny] = s + 1
            q.append((nx, ny, s + 1))  # 移動Bの場合はコスト1. キューの最後尾に追加する.
    
ans = path[Dh][Dw] if path[Dh][Dw] < INF else '-1'
print(ans)
### BUGGY CODE ###

n = int(input())
v = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
ans = 0
for t in range(1, n):
    from itertools import permutations
    a = list(permutations(range(n), t))
    for i in range(len(a)):
        tmp = 0
        for j in a[i]:
            tmp += v[j] - c[j]
        ans = max(ans, tmp)
print(ans)
'''
ans = 0
for i in range(n):
    tmp = v[i] - c[i]
    if tmp > 0:
        ans += tmp
print(ans)
'''

### FIXED CODE ###

#https://atcoder.jp/contests/abc125/tasks/abc125_b

N = int(input())
V = [int(i) for i in input().split()]
C = [int(i) for i in input().split()]
vc = []
for i in range(N):
    vc.append(V[i]-C[i])

vc.sort(reverse=True)
t=0
for i in range(len(vc)):
    if vc[i] > 0:
        t += vc[i]
print(t)
### BUGGY CODE ###

N,K = map(int,input().split())
ary = [0]+list(map(int,input().split()))
dp = [[0]*N for _ in range(N)]
ary = sorted(ary)
a = ary.index(0)
ary.pop(a)
ans = float("Inf")
for i in range(N):
    for j in range(N):
        dp[i][j] = [abs(ary[i]-ary[j]),abs(j-i)]
for i in range(N):
    for j in range(i,N):
        if i == j:
            k = abs(dp[i][i][1] - a)
            d = abs(ary[i])
            if k >= K and ans > d:
                ans = d
            continue
        k = 1 + dp[i][j][1]
        d = abs(ary[i]) + dp[i][j][0]
        if k >= K and ans > d:
            ans = d
print(0 if ans == float("Inf") else ans)

### FIXED CODE ###

N, K = map(int, input().split())
ary = [0] + list(map(int, input().split()))
ary.sort()
zero = ary.index(0)
a = [abs(i - zero) for i in range(N + 1)]
ary.pop(zero)
ans = float("Inf")
for i in range(N - K + 1):
    b = N - i - 1
    d = abs(ary[i])
    if a[i] >= K:
        ans = min(ans, d)
    ans = min(ans, d + abs(ary[i] - ary[i + K - 1]))
    d = abs(ary[b])
    if a[b] >= K:
        ans = min(ans, d)
    ans = min(ans, d + abs(ary[b] - ary[b - K + 1]))
print(ans)