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

from bisect import bisect_left, bisect_right
def main():
    N, Q = map(int, input().split())
    kouji = [list(map(int, input().split())) for _ in range(N)]
    D = [int(input()) for _ in range(Q)]
    ans = [[-1, i+1] for i in range(Q)]
    kouji.sort(key=lambda x: (x[2], x[0]))
    for i in range(N):
        S, T, X = kouji[i]
        L = S-X
        R = T-X-1
        L_idx = bisect_left(D, L)
        R_idx = bisect_right(D, R)
        p = L_idx
        while p < Q and p < R_idx:
            if ans[p][0] == -1:
                ans[p][0] = X
            pre = p
            p = ans[p][1]
            ans[pre][1] = max(ans[pre][1], R_idx)
    for i in range(Q):
        print(ans[i][0])


if __name__ == "__main__":
    main()

### FIXED CODE ###

from bisect import bisect_left
import sys
input = sys.stdin.readline
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if self.parents[x] > self.parents[y]:
            x, y = y, x
        self.parents[x] += self.parents[y]
        self.parents[y] = x
    def same(self, x, y):
        return self.find(x) == self.find(y)
def main():
    N, Q = map(int, input().split())
    kouji = [list(map(int, input().split())) for _ in range(N)]
    D = [int(input()) for _ in range(Q)]
    ans = [-1]*Q
    nxt = [i+1 for i in range(Q)]
    uf = UnionFind(Q)
    kouji.sort(key=lambda x: x[2])
    for i in range(N):
        S, T, X = kouji[i]
        L = S-X
        R = T-X-1
        L_idx = bisect_left(D, L)
        R_idx = bisect_left(D, R+1)
        p = L_idx
        while p < R_idx:
            if ans[p] == -1:
                ans[p] = X
                uf.union(L_idx, p)
                nxt[p] = R_idx
                p += 1
            else:
                par = uf.find(p)
                p = nxt[par]
                uf.union(L_idx, par)
                par = uf.find(par)
                if nxt[par] < R_idx:
                    nxt[par] = R_idx
                if nxt[par] < p:
                    nxt[par] = p
    for i in range(Q):
        print(ans[i])

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

n,p = map(int, input().split())
a = int((p)**(1/n)+1)
for i in range(a,0,-1):
  if p%(i**n)==0:
    print(i)
    exit(0)

### FIXED CODE ###

n,p = map(int, input().split())
a = round(p**(1/n))
for i in range(a,-1,-1):
  if p%(i**n)==0:
    print(i)
    exit()
### BUGGY CODE ###

N = int(input())
List = list(map(int, input().split()))
res = 0
List.sort()
K = List[N-1]+1
Flag = [1]*K
for i in List:
  if Flag[i] ==1:
    res +=1
    for j in range(i,K,i):
      Flag[j] = 0
    if List.count(i) > 1:
      res += -1
print(res)

### FIXED CODE ###

N = int(input())
List = list(map(int, input().split()))
res = 0
List.sort()
K = List[N-1]+1
Flag = [1]*K
for i in range(N):
  if Flag[List[i]] ==1:
    res +=1
    for j in range(List[i],K,List[i]):
      Flag[j] = 0
    if i != N-1 and List[i] == List[i+1]:
      res += -1
print(res)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())
maze = [input() for i in range(H)]

def bfs(maze, sy, sx, gy, gx):
    visited = [[-1]*W for j in range(H)]
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        y, x = queue.popleft()
        if [y, x] == [gy, gx]:
            return visited[y][x]
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1 :
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
ma=0
for sy in range(H):
    for sx in range(W):
        for gy in range(H):
            for gx in range(W):
                if maze[sy][sx] == "." and maze[gy][gx] == ".":
                    if bfs(maze,sy,sx,gy,gx) is not None:
                        ma = max(bfs(maze, sy, sx, gy, gx),ma)
print(ma)


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
maze = [input() for i in range(H)]

def bfs(maze, sy, sx):
    visited = [[-1]*W for j in range(H)]
    queue = deque([[sy, sx]])
    visited[sy][sx] = 0
    while queue:
        ans=0
        y, x = queue.popleft()
        for j, k in ([1, 0], [-1, 0], [0, 1], [0, -1]):
            new_y, new_x = y+j, x+k
            if 0 <= new_y < H and 0 <= new_x < W:
                if maze[new_y][new_x] == "." and visited[new_y][new_x] == -1 :
                    visited[new_y][new_x] = visited[y][x] + 1
                    queue.append([new_y, new_x])
                    
    for l in range(H):
        for m in range(W):
            ans = max(ans,visited[l][m])
            
    return ans
        
ma=0
for sy in range(H):
    for sx in range(W):
        if maze[sy][sx] == ".":
            if bfs(maze,sy,sx) is not None:
                ma = max(bfs(maze, sy, sx),ma)
print(ma)
### BUGGY CODE ###

def sol():
    h,w=map(int,input().split())
    l=[]
    x=[[0]*w for i in range(h)]
    y=[[0]*w for i in range(h)]
    for i in range(h):
        s=input()
        l.append(s)
    for i in range(h):
        for j in range(w):
            if j==0 and l[i][j]==".":
                x[i][j]=1
            elif l[i][j]==".":
                x[i][j]=x[i][j-1]+1
    for i in range(h):
        for j in range(1,w):
            t=-1*(j+1)
            if l[i][t]==".":
                x[i][t]=max(x[i][t],x[i][t+1])

    for i in range(w):
        for j in range(h):
            if j==0 and l[j][i]==".":
                y[j][i]=1
            elif l[j][i]==".":
                y[j][i]=y[j-1][i]+1
    for i in range(w):
        for j in range(1,h):
            t=-1*(j+1)
            if l[t][i]==".":
                y[t][i]=max(y[t][i],y[t+1][i])
    ans=chk=0
    for i in range(h):
        for j in range(w):
            ans=max(ans,x[i][j]+y[i][j]-1)
    print(ans)

if __name__=="__main__":
    sol()


### FIXED CODE ###

def sol():
    h,w=map(int,input().split())
    l=[]
    x=[[0]*w for i in range(h)]
    y=[[0]*w for i in range(h)]
    for i in range(h):
        s=input()
        l.append(s)
    for i in range(h):
        for j in range(w):
            if j==0 and l[i][j]==".":
                x[i][j]=1
            elif l[i][j]==".":
                x[i][j]=x[i][j-1]+1
    for i in range(h):
        for j in range(1,w):
            t=-1*(j+1)
            if l[i][t]==".":
                x[i][t]=max(x[i][t],x[i][t+1])

    for i in range(w):
        for j in range(h):
            if j==0 and l[j][i]==".":
                y[j][i]=1
            elif l[j][i]==".":
                y[j][i]=y[j-1][i]+1
    for i in range(w):
        for j in range(1,h):
            t=-1*(j+1)
            if l[t][i]==".":
                y[t][i]=max(y[t][i],y[t+1][i])
    ans=chk=0
    for i in range(h):
        for j in range(w):
            ans=max(ans,x[i][j]+y[i][j]-1)
    print(ans)

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

from collections import Counter

S = [int(i) for i in input()]
S.reverse()
lst = []
_sum = 0

for i in range(len(S)):
    _sum = (_sum + S[i] * 10**i % 2019) % 2019
    lst.append(_sum)
    
C = Counter(lst)    
ans = C[0]

for i in C:
    ans += C[i]*(C[i]-1)//2
print(ans)    


### FIXED CODE ###

from collections import Counter

S = [int(i) for i in input()]
S.reverse()
lst = []
_sum = 0

for i in range(len(S)):
    _sum = (_sum + S[i] * pow(10,i,2019)) % 2019
    lst.append(_sum)
    
C = Counter(lst)    
ans = C[0]

for i in C:
    ans += C[i]*(C[i]-1)//2
print(ans)
### BUGGY CODE ###

import math
import fractions
from functools import reduce

def loop1(i, k, ans):
  global arr, result
  for ai in range(int(math.floor(k/arr[i])+1)):
    if (i+1<len(arr)):
      loop1(i+1, k-arr[i]*ai, ans+[ai])
    else:
      if arr[i]*ai==k:
        result=ans+[ai]
        break
  return result

def gcd(*arr):
  return reduce(fractions.gcd, arr)

def loop2(i, k, ans):
  global arr, result
  if k%gcd(*arr[i:len(arr)])==0:
    for ai in range(int(math.floor(k/arr[i])+1)):
      if i+1<len(arr):
        loop2(i+1, k-arr[i]*ai, ans+[ai])
      else:
        result=(ans+[ai])
        break
  return result


arr=[100, 101, 102, 103, 104, 105]
k=int(input())
result=""
loop2(0, k, [])
if result=="":
  print(0)
else:
  print(1)

### FIXED CODE ###

import math
import fractions
from functools import reduce

def loop1(i, k, ans):
  global arr, result
  for ai in range(int(math.floor(k/arr[i])+1)):
    if (i+1<len(arr)):
      loop1(i+1, k-arr[i]*ai, ans+[ai])
    else:
      if arr[i]*ai==k:
        result=ans+[ai]
        break
  return result

def gcd(*arr):
  return reduce(fractions.gcd, arr)

def loop2(i, k, ans):
  global arr, result
  if k%gcd(*arr[i:len(arr)])==0:
    for ai in range(int(math.floor(k/arr[i])+1)):
      if i+1<len(arr):
        loop2(i+1, k-arr[i]*ai, ans+[ai])
      else:
        result=(ans+[ai])
        break
  return result


arr=[100, 101, 102, 103, 104, 105]
k=int(input())
result=""
if k>=2200:
  print(1)
else:
  loop2(0, k, [])
  if result=="":
    print(0)
  else:
    print(1)
### BUGGY CODE ###

n = int(input())
mod = 10**9 + 7
ans = 1
for i in range(1,n + 1):
  ans *= i
#print(ans % mod)
print(ans%mod)

### FIXED CODE ###

n = int(input())
mod = 10**9 + 7
ans = 1
for i in range(1,n + 1):
  ans = i * ans % mod
print(ans)
### BUGGY CODE ###

S = input()
T = [s for s in S]
cnt=0
while not (all(t=='W' for t in T) or all(t=='B' for t in T)):
    if(T[0]=='W'):
        cnt+=1
        T = ['B'] + T
        for i in range(1,len(T)):
            if T[i]=='W':
                T[i]='B'
            else:
                break
    else:
        cnt+=1
        T = ['W'] + T
        for i in range(1,len(T)):
            if T[i]=='B':
                T[i]='W'
            else:
                break
print(cnt)


### FIXED CODE ###

S = input()
cnt=0
for i in range(len(S)-1):
    if S[i]!=S[i+1]: cnt+=1
print(cnt)
### BUGGY CODE ###

import heapq
n,m = map(int,input().split())
a = [int(i) for i in input().split()]
b = [[int(i) for i in input().split()] for _ in range(m)]

heapq.heapify(a)
c = 0
for i in range(m) :
    B = b[i][0]
    C = b[i][1]
    for i in range(B) :
        if a[0] < C :
            heapq.heappop(a)
            c += 1
        else :
            break
    for i in range(c) :
        heapq.heappush(a,C)
    c = 0

print(sum(a))

### FIXED CODE ###

n,m = map(int,input().split())
a = [int(i) for i in input().split()]
b = [[int(i) for i in input().split()] for _ in range(m)]
a.sort()
b = sorted(b,key = lambda  x: x[1],reverse=True)
d = []
j = 0
while (n<=len(a) or j<m) :
    C = b[j][1]
    B = b[j][0]
    for i in range(B) :
        d.append(C)
    j += 1
    if j>=m or len(d) > len(a) :
        break

for i in range(min(len(d),len(a))) :
    if a[i] < d[i] :
        a[i] = d[i]

print(sum(a))
### BUGGY CODE ###

n=int(input())
pos=n//2-1
arr=list(map(int,input().split()))
for i in range(n):
  arr[i]=[arr[i],i]
arr=sorted(arr,key=lambda x:x[0])
ans=[0]*n
for i in range(n):
  tmp=arr[:i]+arr[i+1:]
  ans[arr[i][1]]=tmp[pos][0]
for i in range(n):
  print(ans[i])

### FIXED CODE ###

n=int(input())
pos=n//2-1
arr=list(map(int,input().split()))
for i in range(n):
  arr[i]=[arr[i],i]
arr=sorted(arr,key=lambda x:x[0])
ans=[0]*n
for i in range(n):
  if i<=pos:
    ans[arr[i][1]]=arr[pos+1][0]
  else:
    ans[arr[i][1]]=arr[pos][0]
for i in range(n):
  print(ans[i])
### BUGGY CODE ###

def addbit(i):
    i += 1
    while i <= N:
        BIT[i] += 1
        i += i & (-i)
def getsum(i):
    ret = 0
    i += 1
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret
def bit(L):
    global BIT
    BIT=[0] * (N+1)
    re = 0
    for l in L:
        re += getsum(l)
        addbit(l)
    return N*(N-1)//2 - re
def calc(Z):
    Z.sort()
    l, r, lc, rc = -1<<20, 1<<20, N*(N-1)//4+1, N*(N-1)//4+1
    if N <= 10000: l, r = -1<<28, 1<<28
    while r - l > 0.000000001:
        m = (l * rc + r * lc) / (lc + rc)
        A = [a&((1<<16)-1) for a in sorted([(int((s*m+t)*2**40)<<16)+i for i, (s, t) in enumerate(Z)])]
        c = bit(A)
        if c > N*(N-1)//4:
            l = m
            lc = ((c - N*(N-1)//4) * 2) ** 0.5
        else:
            r = m
            rc = ((N*(N-1)//4 - c) * 2 + 1) ** 0.5
    return l

N = int(input())
X, Y = [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    X.append((-a/b, c/b))
    Y.append((-b/a, c/a))
print(calc(X), calc(Y))

### FIXED CODE ###

def addbit(i):
    i += 1
    while i <= N:
        BIT[i] += 1
        i += i & (-i)
def getsum(i):
    ret = 0
    i += 1
    while i != 0:
        ret += BIT[i]
        i -= i&(-i)
    return ret
def bit(L):
    global BIT
    BIT=[0] * (N+1)
    re = 0
    for l in L:
        re += getsum(l)
        addbit(l)
    return N*(N-1)//2 - re
def calc(Z):
    Z.sort()
    l, r, lc, rc = -1<<28, 1<<28, N*(N-1)//4+1, N*(N-1)//4+1
    f = 1
    while (r - l) / max(abs(l), 1) > 0.000000001:
        m = (l+r) / 2 if f else (l * rc + r * lc) / (lc + rc)
        A = [a&((1<<16)-1) for a in sorted([(int((s*m+t)*2**40)<<16)+i for i, (s, t) in enumerate(Z)])]
        c = bit(A)
        if c > N*(N-1)//4:
            l = m
            lc = (c - N*(N-1)//4) * 2
        else:
            r = m
            rc = (N*(N-1)//4 - c) * 2 + 1
        f ^= 1
    return l

N = int(input())
X, Y = [], []
for _ in range(N):
    a, b, c = map(int, input().split())
    X.append((-a/b, c/b))
    Y.append((-b/a, c/a))
print(calc(X), calc(Y))
### BUGGY CODE ###

H, W, M = map(int, input().split())
hList = {i+1: 0 for i in range(H)}
wList = {i+1: 0 for i in range(W)}
pList = set()
#print(hList, wList, pList)
for _ in range(M):
  h, w = list(map(int, input().split()))
  #print(h, w)
  hList[h] += 1
  wList[w] += 1
  pList.add((h, w))
#print(hList, wList, pList)

#maxCount = 0
#for h, count in hList.items():
#  if maxCount<count:
#    maxCount = count
maxCount = max(hList.values())
maxHList = [h for h, count in hList.items() if count==maxCount]


#maxCount = 0
#for w, count in wList.items():
#  if maxCount<count:
#    maxCount = count
maxCount = max(wList.values())
maxWList = [w for w, count in wList.items() if count==maxCount]

counterList = []
for maxH in maxHList:
  for maxW in maxWList:
    counterList.append(hList[maxH] + wList[maxW] - (1 if ((maxH, maxW) in pList) else 0))
    #counter = 0
    #for h, w in pList:
    #  #print(h, maxH, w, maxW)
    #  if h==maxH or w==maxW:
    #    counter += 1
    #counterList.append(counter)
print(max(counterList))


### FIXED CODE ###

import sys
H, W, M = map(int, input().split())
hList = {i+1: 0 for i in range(H)}
wList = {i+1: 0 for i in range(W)}
pList = set()
#print(hList, wList, pList)
for _ in range(M):
  h, w = list(map(int, input().split()))
  #print(h, w)
  hList[h] += 1
  wList[w] += 1
  pList.add((h, w))
#print(hList, wList, pList)

maxHCount = max(hList.values())
maxHList = [h for h, count in hList.items() if count==maxHCount]


maxWCount = max(wList.values())
maxWList = [w for w, count in wList.items() if count==maxWCount]

#counterList = []
#for maxH in maxHList:
#  for maxW in maxWList:
#    counterList.append(hList[maxH] + wList[maxW] - (1 if ((maxH, maxW) in pList) else 0))
#print(max(counterList))
#print(max(((hList[maxH] + wList[maxW] - (1 if ((maxH, maxW) in pList) else 0)) for maxH in maxHList for maxW in maxWList)))
#print(max(((hList[maxH] + wList[maxW] - (1 if ((maxH, maxW) in pList) else 0)) for maxH in maxHList for maxW in maxWList)))

#if M < len(maxHList)*len(maxWList):
#	print(maxHCount + maxWCount)
#	sys.exit(0)

for maxH in maxHList:
  for maxW in maxWList:
    if (maxH, maxW) not in pList:
      print(maxHCount + maxWCount)
      sys.exit(0)

print(maxHCount + maxWCount - 1)
### BUGGY CODE ###

it = input()
it = it.split()
n = int(it[0])
m = int(it[1])
p = [[] for _ in range(n)]
for _ in range(m):
    itf = input()
    itf = itf.split()
    a = int(itf[0])
    b = int(itf[1])
    p[a-1].append(b)
    p[b-1].append(a)
d = [1, ]
con = [0] * n
l = 0
while d:
    for i, k in enumerate(p[1:]):
        if con[i]!=0:continue
        if d[0] in k:
            d.append(i+2)
            con[i] = d[l]
    if len(d) > 1:
        d.pop(0)
    else:
        break
print('Yes')
for i in range(n-1):
    print(con[i])

### FIXED CODE ###

it = input()
it = it.split()
n = int(it[0])
m = int(it[1])
p = [[] for _ in range(n)]
for _ in range(m):
    itf = input()
    itf = itf.split()
    a = int(itf[0])
    b = int(itf[1])
    p[a-1].append(b)
    p[b-1].append(a)
d = [1, ]
con = [0] * n
while d:
    l = d.pop(0)
    for k in p[l-1]:
        if con[k-2]==0:
            d.append(k)
            con[k-2] = l
print('Yes')
for i in range(n-1):
    print(con[i])
### BUGGY CODE ###

N = int(input())
sum = 0
for i in range(1, N):
    sum += i
if N == 1:
    print(0)
else:
    print(sum)

### FIXED CODE ###

N = int(input())
if N == 1:
    print(0)
else:
    print(N*(N-1)//2)
### BUGGY CODE ###

N = int(input())
S = list(str(input()))

def ordN(x):
  return ord(x) - ord('a')

li = [[] for _ in range(26)]
for i,s in enumerate(S):
  li[ordN(s)].append(i)

for i in range(int(input())):
  Q1, Q2, Q3 = input().split()
  if Q1 == "1":
    Q2 = int(Q2) - 1
    if S[Q2] != Q3:
      li[ordN(S[Q2])] = [n for n in li[ordN(S[Q2])] if n != Q2]
      li[ordN(Q3)].append(Q2)
      S[Q2] = Q3
  else:
    Q2, Q3 = int(Q2)-1, int(Q3)-1
    count = 0
    for j in range(26):
      if [True for n in li[j] if Q2 <= n and n <= Q3]:
        count += 1
    print(count)

### FIXED CODE ###

import bisect

N = int(input())
S = list(str(input()))

def ordN(x):
  return ord(x) - ord('a')

li = [[] for _ in range(26)]
for i,s in enumerate(S):
  li[ordN(s)].append(i)

for i in range(int(input())):
  Q1, Q2, Q3 = input().split()
  if Q1 == "1":
    Q2 = int(Q2) - 1
    if S[Q2] != Q3:
      I = bisect.bisect_left(li[ordN(S[Q2])], Q2)
      li[ordN(S[Q2])].pop(I)
      bisect.insort(li[ordN(Q3)], Q2)
      S[Q2] = Q3
  else:
    Q2, Q3 = int(Q2)-1, int(Q3)-1
    count = 0
    for j in range(26):
      I = bisect.bisect_left(li[j], Q2)
      if I < len(li[j]) and li[j][I] <= Q3:
        count += 1
    print(count)
### BUGGY CODE ###

a,b=open(0);c=1;
for i in b.split():c=[d:=int(i)*c,-1][10**18<d or d*c<0]
print(c)

### FIXED CODE ###

a,b=open(0);c=1;
for i in sorted(b.split()):
    c*=int(i)
    if c>10**18:print(-1);exit()
print(c)
### BUGGY CODE ###

import heapq
from collections import defaultdict

n, m, s, t = list(map(int, input().split()))

graph_y = defaultdict(list)
graph_s = defaultdict(list)

for i in range(m):
	u, v, a, b = list(map(int, input().split()))
	graph_y[u - 1].append([v - 1, a])
	graph_y[v - 1].append([u - 1, a])
	graph_s[u - 1].append([v - 1, b])
	graph_s[v - 1].append([u - 1, b])

dist_node_ys = [float("inf") for i in range(n)]
dist_node_ys[s - 1] = 0

Q = []
heapq.heappush(Q, (dist_node_ys[s - 1], s - 1))

while Q: 
	dis, v= heapq.heappop(Q)
	if dist_node_ys[v] < dis:
		continue
	for u, w in graph_y[v]:
		alt = dis + w
		if dist_node_ys[u] > alt:
			dist_node_ys[u] = alt
			heapq.heappush(Q, (alt, u))

dist_node_st = [float("inf") for i in range(n)]
dist_node_st[t - 1] = 0

Q = []
heapq.heappush(Q, (dist_node_st[t - 1], t - 1))

while Q: 
	dis, v = heapq.heappop(Q)
	if dist_node_st[v] < dis:
		continue
	for u, w in graph_s[v]:
		alt = dis + w
		if dist_node_st[u] > alt:
			dist_node_st[u] = alt
			heapq.heappush(Q, (alt, u))

ansL = []
X = []
for i in range(n):
	heapq.heappush(X, dist_node_ys[n - 1 - i] + dist_node_st[n - 1 - i])
	ansL.append(X[0])

for i in range(1, n + 1):
	print(1000000000000000 - ansL[- i])


### FIXED CODE ###

import heapq
from collections import defaultdict

n, m, s, t = list(map(int, input().split()))

graph_y = defaultdict(dict)
graph_s = defaultdict(dict)

for i in range(m):
	u, v, a, b = list(map(int, input().split()))
	graph_y[u - 1][v - 1] = a
	graph_y[v - 1][u - 1] = a
	graph_s[u - 1][v - 1] = b
	graph_s[v - 1][u - 1] = b

dist_node_ys = defaultdict(lambda: float("inf"))
dist_node_ys[s - 1] = 0

Q = []
heapq.heappush(Q, (dist_node_ys[s - 1], s - 1))

while Q: 
	dis, v = heapq.heappop(Q)
	if dist_node_ys[v] < dis:
		continue
	for i in graph_y[v]:
		u = i
		w = graph_y[v][i]
		alt = dis + w
		if dist_node_ys[u] > alt:
			dist_node_ys[u] = alt
			heapq.heappush(Q, (alt, u))


dist_node_st = defaultdict(lambda: float("inf"))
dist_node_st[t - 1] = 0

Q = []
heapq.heappush(Q, (dist_node_st[t - 1], t - 1))

while Q: 
	dis, v = heapq.heappop(Q)
	if dist_node_st[v] < dis:
		continue
	for i in graph_s[v]:
		u = i
		w = graph_s[v][i]
		alt = dis + w
		if dist_node_st[u] > alt:
			dist_node_st[u] = alt
			heapq.heappush(Q, (alt, u))

ansL = []
X = []
for i in range(n):
	heapq.heappush(X, dist_node_ys[n - 1 - i] + dist_node_st[n - 1 - i])
	ansL.append(X[0])

for i in range(1, n + 1):
	print(1000000000000000 - ansL[- i])
### BUGGY CODE ###

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

r = []
if n % k == 0:
    print(0)
    exit()
while True:
    n = abs(n - k)
    r.append(n)
    if r.count(n) >= 2:
        break

print(min(r))


### FIXED CODE ###

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

r = []
n = n % k
if n == 0:
    print(0)
    exit()
while True:
    n = abs(n - k)
    r.append(n)
    if r.count(n) >= 2:
        break

print(min(r))
### BUGGY CODE ###

n,k = map(int,input().split())
ls = []

for i in range(n):
    a,b = [int(i) for i in input().split()]
    tmp = [a] * b
    ls.append(tmp)

ls = sum(ls,[])
ls.sort()
print(ls[k-1])

### FIXED CODE ###

n,k = map(int,input().split())
ls = []

for i in range(n):
    a,b = [int(i) for i in input().split()]
    ls.append([a,b])

ls.sort()
for a,b in ls:
    if b >= k:
        print(a)
        break
    else:
        k -= b
### 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 combinations
    a = list(combinations(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)