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

from heapq import heappush, heappop
import itertools
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[10000000000 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))
while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])


### FIXED CODE ###

from heapq import heappush, heappop
sx,sy,gx,gy=map(int,input().split())
n=int(input())
g = [[] for i in range(n+2)]
data=[(sx+sy*1j,0)]
for i in range(n):
    a,b,c=map(int,input().split())
    data.append((a+b*1j,c))
data.append((gx+gy*1j,0))

for i in range(n+2):
    for j in range(i+1,n+2):
        tmp=abs(data[i][0]-data[j][0])-data[i][1]-data[j][1]
        g[i].append((tmp,j))
        g[j].append((tmp,i))

dist=[2828427127 for i in range(n+2)]
visited=[False for i in range(n+2)]
dist[0]=0
que=[]
heappush(que,(0,0))

while que:
    c,v=heappop(que)
    if visited[v]:
        continue
    visited[v]=True
    for x in g[v]:
        if visited[x[1]]:
            continue
        tmp=x[0]+c if not x[0]<0 else c
        if tmp<dist[x[1]]:
            dist[x[1]]=tmp
            heappush(que,(tmp,x[1]))
print(dist[n+1])
### BUGGY CODE ###

# 関数ラップするだけで倍近く早くなった…

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

def main():
  # Worst Case
  #n,k=100000,100
  #a=[p for p in range(100000)]
  
  kl=[p for p in range(1,k+1)]
  dp=[float("inf")]*(n)
  dp[0]=0
  for i in range(n):
    for j in kl:
      ij=i+j
      if ij < n:
        m=dp[i]+abs(a[i]-a[ij])
        if m < dp[ij]:
          dp[ij]=m

  print(dp[n-1])

main()

### FIXED CODE ###

n,k=map(int,input().split())
a=list(map(int,input().split()))
#n,k=100000,100
#a=[i for i in range(100000)]

kl=[i for i in range(1,k+1)]

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

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

N=int(input())
H=list(map(int,input().split()))
a=0
h=0
for i in range(N-1):
    for j in range(1,N-i):
        h=H[i]-H[i+j]
        if h>=2:
            a=1
            break
    if a==1:
        break
if a==0:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

N=int(input())
H=list(map(int,input().split()))
a=0
for i in range(N-1)[::-1]:
    if H[i]>H[i+1]:
        H[i]-=1
for i in range(N-1):
    if H[i]>H[i+1]:
        a=1
        break
if a==0:
    print("Yes")
else:
    print("No")
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpl()
ans = 0
a.sort()
for i in range(n-2):
    for j in range(i+1,n-1):
        b = a[j+1:]
        tmp = a[i] + a[j] - 1
        tt = bisect.bisect_right(b,tmp)
        # print(i,j,tmp,tt,b)
        if tmp >= a[-1]:
            ans += tt
        elif tt > 0 :
            ans += tt
        
print(ans)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue
sys.setrecursionlimit(10**8)
mod = 10**9+7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
def inpln(n): return list(int(sys.stdin.readline()) for i in range(n))

n = inp()
a = inpl()
ans = 0
a.sort()
for i in range(n-2):
    for j in range(i+1,n-1):
        b = a[j+1:]
        tmp = a[i] + a[j] - 1
        tt = bisect.bisect_right(b,tmp)
        if tt > 0 :
            ans += tt
print(ans)
### BUGGY CODE ###



a,b,x = map(int, input().split())

ret = 0
for i in range(a,b+1):
  if i%x==0:
    ret += 1
print(ret)  

### FIXED CODE ###

a,b,x = map(int, input().split())
print(b//x-(a-1)//x)
### BUGGY CODE ###

n=int(input())
print(1)
s=input()
if s="Vacant":
  exit(0)

l=1
r=n

for i in range(20):

  if r-l<=2:
    for i in range(3):
      print(l+1)
      s=input()
      if s="Vacant":
        exit(0)

      
  elif (r-l+1)%4==1:
    print((l+r)//2)
    sn=input()
    if sn="Vacant":
      exit(0)
    elif s==sn:
      l=(l+r)//2
    else:
      r=(l+r)//2
    s=sn

  else:
    print((l+r)//2-1)
    sn=input()
    if sn="Vacant":
      exit(0)
    elif s==sn:
      l=(l+r)//2-1
    else:
      r=(l+r)//2-1
    s=sn
      
      
      
      

### FIXED CODE ###

n=int(input())
print(0, flush=True)
sl=input()
if sl=="Vacant":
  exit(0)

l=0
r=n-1

for i in range(30):

  if r-l<=2:
    for j in range(3):
      print(l+j+1, flush=True)
      s=input()
      if s=="Vacant":
        exit(0)

      
  elif ((l+r)//2)%2==0:
    print((l+r)//2, flush=True)
    s=input()
    if s=="Vacant":
      exit(0)
    elif s==sl:
      l=(l+r)//2
      sl=s
    else:
      r=(l+r)//2
      sr=s

  else:
    print((l+r)//2+1, flush=True)
    s=input()
    if s=="Vacant":
      exit(0)
    elif s==sl:
      l=(l+r)//2
      sl=s
    else:
      r=(l+r)//2
      sr=s
### BUGGY CODE ###

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

aaa = 0
list_ans = []
i = 0
while i < n-k+1:
    a = sum(list[i:i+k])
    if aaa <= a:
        aaa = a
        list_ans = list[i:i+k]
    i += 1 

ans = 0
i = 0
while i < len(list_ans):
    ans += (list_ans[i]+1)/2
    i += 1

print(ans)  

### FIXED CODE ###

n,k = map(int,input().split())
L = list(map(int,input().split()))
 
aaa = sum(L[0:k])
ans = aaa
for i in range(k,n):
    aaa += L[i]
    aaa -= L[i-k]
    if ans <= aaa:
        ans = aaa
    i += 1    
     
print((ans+k)/2)
### BUGGY CODE ###

N,X = map(int,input().split())
x_list = list(map(int,input().split()))

def gcd(int_list):
    int_list.sort(reverse = True)
    for i in range(1,int_list[0]+1):
        for ii in int_list:
            if ii%i != 0:
                break
        else:
            gdc = i
    return(gdc)

x_list.append(X)
x_list.sort()

x_len = list()
for i in range(1,N+1):
    x_len.append(x_list[i]-x_list[i-1])

print(gcd(x_len))

### FIXED CODE ###

import fractions
import functools

N,X = map(int,input().split())
x_list = list(map(int,input().split()))

x_list.append(X)
x_list.sort()

x_len = list()
for i in range(1,N+1):
    x_len.append(x_list[i]-x_list[i-1])

x_len.sort(reverse = True)

result = functools.reduce(fractions.gcd,x_len)

print(result)
### BUGGY CODE ###

import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

def main():
    N = INT()
    A = LIST()
    x = [0] * N
    xsum = sum(A)
    for i in range(N):
        tmp = 0
        for j in range(N // 2):
            tmp += A[(i+2*j+1)%N] * 2
        x[i] = int(xsum - tmp)
    print(*x)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys

def input(): return sys.stdin.readline()[:-1]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def MATINT(h): return [list(map(int, input().split())) for _ in range(h)]
def MATSTR(h): return [input() for _ in range(h)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
inf = float('inf')
mod = 10 ** 9 + 7

def main():
    N = INT()
    A = LIST()
    x = [0] * N
    sumx = sum(A)
    x[0] = sumx - sum(A[1::2]) * 2
    for i in range(1, N):
        x[i] = A[i - 1] * 2 - x[i - 1]
    print(*x)

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

from collections import Counter

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

l = []
r = []
for i, ai in enumerate(a):
   l.append(i+ai)
   r.append(i-ai)

ans = 0
for i in l:
   ans += r.count(i)

print(ans)


### FIXED CODE ###

from collections import Counter

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

l = []
r = []
for i, ai in enumerate(a):
   l.append(i+ai)
   r.append(i-ai)

ans = 0
b = Counter(r)
for i in l:
   ans += b.get(i, 0)

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

A, B = [int(i) for i in input().split()]

def gcd(x, y):
    r = x % y
    while r > 0:
        x = y
        y = r
        r = x % y
    
    return y

def cd (x, y):
    a = gcd(x, y)

    cd_list = []
    for i in range(1, a + 1):
        if a % i == 0:
            cd_list.append(i)

    return cd_list

cd_list = cd(A, B)
f_list = [0] * len(cd_list)
for i in range(1, len(cd_list) - 1):
    for j in range(i + 1, len(cd_list)):
        if cd_list[j] % cd_list[i] == 0:
            f_list[j] = 1
    
count = 0
for i in range(len(f_list)):
    if f_list[i] == 0:
        count += 1

print(count)

### FIXED CODE ###

def make_divisors(n):

    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()

    return divisors

def is_remainder(n):
    if n == 1:
        return True

    for i in range(2, int(n**0.5)+1):
        if n % i == 0:
            return False
    
    return True
        

A, B = [int(i) for i in input().split()]

import fractions
n = fractions.gcd(A, B)
divisors = make_divisors(n)
N = len(divisors)

count = 0
flag = [0] * N
for item in divisors:
    if is_remainder(item):
        count += 1

print(count)
### BUGGY CODE ###

n = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())

def trade(n, rate):
    dp = [0]
    for i in range(n):
        v = dp[i] + 1
        for ra, rb in rate:
            if i + 1 >= ra:
                v = max(v, dp[i + 1 - ra] + rb)
        dp.append(v)
    return dp[-1]

n = trade(n, [(ga, gb), (sa, sb), (ba, bb)])
n = trade(n, [(gb, ga), (sb, sa), (bb, ba)])
print(n)


### FIXED CODE ###

n = int(input())
ga, sa, ba = map(int, input().split())
gb, sb, bb = map(int, input().split())

def trade(n, rate):
    dp = [0]
    r = sorted(rate, key=lambda r: float(r[0]) / float(r[1]))[0]
    p = n - 10000000
    if p // r[0] > 0:
        d = p // r[0]
        n -= d * r[0]
        dp = [d * r[1]]
    for i in range(n):
        v = dp[i] + 1
        for ra, rb in rate:
            if i + 1 >= ra:
                v = max(v, dp[i + 1 - ra] + rb)
        dp.append(v)
    return dp[-1]

n = trade(n, [(ga, gb), (sa, sb), (ba, bb)])
n = trade(n, [(gb, ga), (sb, sa), (bb, ba)])
print(n)
### BUGGY CODE ###

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

aa = [0 for i in range(2*10**5)]
for i in range(n):
  aa[a[i]] += 1
 
for i in range(n):
  ans = 0
  aa[a[i]] -= 1
  for key in range(2*10**5):
    if aa[key] > 1:
      ans += aa[key]*(aa[key]-1)//2
  aa[a[i]] += 1
  print(ans)
  



### FIXED CODE ###

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

aa = [0 for i in range(2*10**5)]
for i in range(n):
  aa[a[i]] += 1
 
ans = 0
for key in range(2*10**5):
  ans += aa[key]*(aa[key]-1)//2
    
for i in range(n):
  tmp1 = aa[a[i]]*(aa[a[i]]-1)//2
  aa[a[i]] -= 1
  tmp2 = aa[a[i]]*(aa[a[i]]-1)//2
  aa[a[i]] += 1
  print(ans-tmp1 + tmp2)
### BUGGY CODE ###

from collections import Counter
N=int(input())
s=[0 for _ in range(N)]
count=0
for i in range(N):
    s[i]=input()
for t in range(N):
    for i in range(N):
        if t>=i:
            continue
        if Counter(s[t])==Counter(s[i]):
            count+=1
        if i==t:
            count-=1
print(int((count)))

### FIXED CODE ###

N=int(input())
S=[''.join(sorted((input()))) for i in range(N)]
P={}
for i in range(N):
    if S[i] in P:
        P[S[i]]+=1
    else:
        P[S[i]]=0
for i in P.keys():
    if P[i]>=2:
        P[i]=P[i]*(P[i]+1)/2
print(int(sum(P.values())))
### BUGGY CODE ###

N, C = map(long, raw_input().split())
Sushi  = [map(long, raw_input().split()) for i in range(N)]
Sushi_rev = []
for s in Sushi[::-1]:
  Sushi_rev.append([C-s[0], s[1]])
Sushi.insert(0L, [0L, 0L])
Sushi_rev.insert(0L, [0L, 0L])
N += 1
ans = 0
cal_clock = []
tmp = 0
for i in Sushi:
  tmp += i[1]
  cal_clock.append(tmp)
cal_anticlock = []
tmp = 0
for i in Sushi_rev:
  tmp += i[1]
  cal_anticlock.append(tmp)
ans = 0
for a in range(N):
  for b in range(N-a):
    oa = Sushi[a][0]
    ob = Sushi_rev[b][0]
    eaten = cal_clock[a]+cal_anticlock[b]
    get_cal_oab = eaten - (2 * oa +ob)
    get_cal_oba = eaten - (2 * ob +oa)
    get_cal = eaten - (oa+ob) - (oa if oa < ob else ob)
    if get_cal > ans:
      ans = get_cal
print ans


### FIXED CODE ###

N, C = map(long, raw_input().split())
Sushi_clock  = [map(long, raw_input().split()) for i in range(N)]
Sushi_anticlock = [[C-x[0], x[1]] for x in Sushi_clock[::-1]]
Sushi_clock.insert(0, [0L, 0L])
Sushi_anticlock.insert(0, [0L, 0L])
N += 1
ans = 0
eatcal = 0
getcal_clock_max = 0
getcal_clock_max_oa = 0
getcal_clock_maxes = []
getcal_clock2_max = 0
getcal_clock2_max_oa = 0
getcal_clock2_maxes = []
for i in Sushi_clock:
  eatcal += i[1]
  getcal = eatcal-i[0]
  getcal_clock_max_oa = i[0] if getcal > getcal_clock_max else getcal_clock_max_oa
  getcal_clock_max = getcal if getcal > getcal_clock_max else getcal_clock_max
  getcal_clock_maxes.append([getcal_clock_max,getcal_clock_max_oa])
  getcal2 = eatcal-i[0]*2
  getcal_clock2_max_oa = i[0] if getcal2 > getcal_clock2_max else getcal_clock2_max_oa
  getcal_clock2_max = getcal2 if getcal2 > getcal_clock2_max else getcal_clock2_max
  getcal_clock2_maxes.append([getcal_clock2_max,getcal_clock2_max_oa])
eatcal = 0
for anti, oa, oa2 in zip(Sushi_anticlock, getcal_clock_maxes[::-1], getcal_clock2_maxes[::-1]):
  eatcal += anti[1]
  getcal_oa2 = eatcal-anti[0]+oa2[0]
  getcal_ob2 = eatcal-anti[0]*2+oa[0]
  ans = max(ans, getcal_oa2, getcal_ob2)
print ans
### BUGGY CODE ###

from collections import deque

N = int(input())
A = []
B = []

for i in range(N):

    a = int(input())

    A.append(a)

A.sort()

now = A.pop(0)
L = now
R = now
ans = 0

for i in range(N-1):

    if abs(L-A[0]) == max(abs(L-A[0]),abs(L-A[-1]),abs(R-A[0]),abs(R-A[-1])):
        ans += abs(L-A[0])
        L = A[0]
        A.pop(0)

    elif abs(L-A[-1]) == max(abs(L-A[0]),abs(L-A[-1]),abs(R-A[0]),abs(R-A[-1])): 
        ans += abs(L-A[-1])
        L = A[-1]
        A.pop(-1)

    elif abs(R-A[0]) == max(abs(L-A[0]),abs(L-A[-1]),abs(R-A[0]),abs(R-A[-1])):
        ans += abs(R-A[0])
        R = A[0]
        A.pop(0)

    elif abs(R-A[-1]) == max(abs(L-A[0]),abs(L-A[-1]),abs(R-A[0]),abs(R-A[-1])):
        ans += abs(R-A[-1])
        R = A[-1]
        A.pop(-1)

    else:
        print ("eeror")

    #print (A,L,R,ans)

print (ans)

### FIXED CODE ###

from collections import deque

N = int(input())
A = []
B = []

for i in range(N):

    a = int(input())

    A.append(a)

A.sort()

now = A.pop(0)
L = now
R = now
ans = 0
Lind = 0
Rind = -1

for i in range(N-1):

    if abs(L-A[Lind]) == max(abs(L-A[Lind]),abs(L-A[Rind]),abs(R-A[Lind]),abs(R-A[Rind])):
        ans += abs(L-A[Lind])
        L = A[Lind]
        Lind += 1

    elif abs(L-A[Rind]) == max(abs(L-A[Lind]),abs(L-A[Rind]),abs(R-A[Lind]),abs(R-A[Rind])): 
        ans += abs(L-A[Rind])
        L = A[Rind]
        Rind -= 1

    elif abs(R-A[Lind]) == max(abs(L-A[Lind]),abs(L-A[Rind]),abs(R-A[Lind]),abs(R-A[Rind])):
        ans += abs(R-A[Lind])
        R = A[Lind]
        Lind += 1

    elif abs(R-A[Rind]) == max(abs(L-A[Lind]),abs(L-A[Rind]),abs(R-A[Lind]),abs(R-A[Rind])):
        ans += abs(R-A[Rind])
        R = A[Rind]
        Rind -= 1

    else:
        print ("eeror")

    #print (A,L,R,ans)

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

n = int(input())
a = []
for i in range(n):
    num = int(input())
    if num in a:
        a.remove(num)
    else:
        a.append(num)
print(len(a))


### FIXED CODE ###

n = int(input())
a = set()
for i in range(n):
    num = int(input())
    if num in a:
        a.remove(num)
    else:
        a.add(num)
print(len(a))
### BUGGY CODE ###

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

A = []
for i in range(m):
    A.append(int(input()))
    
dp = [0 for i in range(n + 1)]
dp[0] = 1

for i in range(n+1):
    if not i in A:
        if (dp[i-2] >= 1) and (i-2 >= 0):
            dp[i] += dp[i-2]
        if (dp[i-1] >= 1) and (i-1 >= 0):
            dp[i] += dp[i-1]
        dp[i] = dp[i] % (10 ** 9 + 7)
        
print(dp[-1] % (10 ** 9 + 7))

### FIXED CODE ###

n, m = map(int, input().split())
mod = 10 ** 9 + 7
A = []
for i in range(m):
    A.append(int(input()))
    
dp = [None for i in range(n + 1)]
dp[0] = 1

for a in A:
    dp[a] = 0
    
for i in range(1,n+1):
    if dp[i] != 0:
        dp[i] = 0
        if i >= 2:
            dp[i] += (dp[i-2] + dp[i-1]) % mod
        elif i == 1:
            dp[i] += dp[i-1] % mod
            
print(dp[-1])
### BUGGY CODE ###

#for _ in range(int(input())):
def zeroPad(numberString, zeros, left = True):
    """Return the string with zeros added to the left or right."""
    for i in range(zeros):
        if left:
            numberString = '0' + numberString
        else:
            numberString = numberString + '0'
    return numberString
def karatsubaMultiplication(x ,y):
    """Multiply two integers using Karatsuba's algorithm."""
    #convert to strings for easy access to digits
    x = str(x)
    y = str(y)
    #base case for recursion
    if len(x) == 1 and len(y) == 1:
        return int(x) * int(y)
    if len(x) < len(y):
        x = zeroPad(x, len(y) - len(x))
    elif len(y) < len(x):
        y = zeroPad(y, len(x) - len(y))
    n = len(x)
    j = n//2
    #for odd digit integers
    if (n % 2) != 0:
        j += 1    
    BZeroPadding = n - j
    AZeroPadding = BZeroPadding * 2
    a = int(x[:j])
    b = int(x[j:])
    c = int(y[:j])
    d = int(y[j:])
    #recursively calculate
    ac = karatsubaMultiplication(a, c)
    bd = karatsubaMultiplication(b, d)
    k = karatsubaMultiplication(a + b, c + d)
    A = int(zeroPad(str(ac), AZeroPadding, False))
    B = int(zeroPad(str(k - ac - bd), BZeroPadding, False))
    return A + B + bd
n,k=map(int,input().split())
x=[int(x) for x in input().split()]
ans=[1]*n
ans[0]=x[0]
for i in range(1,k):
  ans[i]=ans[i-1]*x[i]
c=0
for i in range(k,n):
  ans[i]=karatsubaMultiplication(ans[i-1],x[i])
  ans[i]=ans[i]//x[c]
  if ans[i]>ans[i-1]:
    print('Yes')
  else:print('No')
  c+=1


### FIXED CODE ###


n,k=map(int,input().split())
x=[int(x) for x in input().split()]
ans=[1]*n
ans[0]=x[0]
c=0
for i in range(k,n):

  if x[c]<x[i]:
    print('Yes')
  else:print('No')
  c+=1
### BUGGY CODE ###

from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = 0
d = deque()
max_res = -float("inf")
for start in range(n):
    d.append(start)
    count = 0
    res = 0
    while count < k:
        now = d.pop()
        next = p[now]
        d.append(next-1)
        res += c[next-1]
        max_res = max(res, max_res)
        count += 1
print(max_res)


### FIXED CODE ###

from collections import deque
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

if max(c) < 0:
    print(max(c))
    exit()

loop_list = []
visited = [False]*n
d = deque()
for start in range(n):
    if visited[start]:
        continue
    loop = [start]
    d.append(start)
    visited[start] = True
    while True:
        now = d.pop()
        next = p[now]
        d.append(next-1)
        if visited[next-1]:
            loop_list.append(loop)
            break
        else:
            visited[next-1] = True
            loop.append(next-1)
#print(loop_list)

ans = 0
for loop in loop_list:
    len_loop = len(loop)
    S = sum(c[v] for v in loop)
    for a in range(len_loop):
        dist_ab = 0
        cost_ab = -c[loop[a]]
        for b in range(a, a+len_loop):
            b %= len_loop
            cost_ab += c[loop[b]]
            max_cost = cost_ab + max(0, S)*((k-dist_ab)//len_loop)
            ans = max(ans, max_cost)
            dist_ab += 1
            if dist_ab > k:
                break
print(ans)
### BUGGY CODE ###

from collections import deque
H, W = map(int, input().split())  # H行, W列
CY, CX = map(lambda x: int(x)-1, input().split())  # 魔法使いの初期値
DY, DX = map(lambda x: int(x)-1, input().split())  # 目的地
gridgraph = [input() for _ in range(H)]
# print(gridgraph)

q = deque()
q.append([CY, CX])  # スタート地点
# 各頂点について2*2の幅優先する？
INF = float("inf")
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]  # 上下左右
distant = [[INF]*W for _ in range(H)]
# print(distant)
# 更新されるなら追加
distant[CY][CX] = 0
while len(q):
    cy, cx = q.popleft()  # 現在位置
    for dy, dx in adjacent:
        # 新しい位置
        ny = cy+dy
        nx = cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        # 道の場合
        if gridgraph[ny][nx] == ".":
            # 道の場合はコスト0で移動できる
            if distant[ny][nx] > distant[cy][cx]:
                distant[ny][nx] = distant[cy][cx]
                q.append([ny, nx])
    # 周囲5*5の道に+1で到達する
    for i in range(-2, 3, 1):
        for j in range(-2, 3, 1):
            target_y, target_x = cy+i, cx+j
            if target_y < 0 or target_y >= H or target_x < 0 or target_x >= W:
                continue
            else:
                if gridgraph[target_y][target_x] == "." and distant[target_y][target_x] > distant[cy][cx]+1:
                    distant[target_y][target_x] = distant[cy][cx]+1
                    q.append([target_y, target_x])

if distant[DY][DX] == INF:
    print(-1)
else:
    print(distant[DY][DX])


### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())  # H行, W列
CY, CX = map(lambda x: int(x)-1, input().split())  # 魔法使いの初期値
DY, DX = map(lambda x: int(x)-1, input().split())  # 目的地
gridgraph = [input() for _ in range(H)]
# print(gridgraph)

q = deque()
q.append((CY, CX))  # スタート地点
# 各頂点について2*2の幅優先する？
adjacent = [[1, 0], [0, 1], [-1, 0], [0, -1]]  # 上下左右
distant = [[10**10]*W for _ in range(H)]
distant[CY][CX] = 0
warp_y = list(range(-2, 3, 1))
warp_x = list(range(-2, 3, 1))
while len(q):
    cy, cx = q.popleft()  # 現在位置
    for dy, dx in adjacent:
        # 新しい位置
        ny = cy+dy
        nx = cx+dx
        if ny < 0 or ny >= H or nx < 0 or nx >= W:
            continue
        # 道の場合
        if gridgraph[ny][nx] == "." and distant[ny][nx] > distant[cy][cx]:
            # 道の場合はコスト0で移動できる
            distant[ny][nx] = distant[cy][cx]
            q.appendleft((ny, nx))
    # 周囲5*5の道に+1で到達する
    for i in warp_y:
        for j in warp_x:
            target_y, target_x = cy+i, cx+j
            if target_y < 0 or target_y >= H or target_x < 0 or target_x >= W:
                continue
            else:
                if gridgraph[target_y][target_x] == "." and distant[target_y][target_x] > distant[cy][cx]+1:
                    distant[target_y][target_x] = distant[cy][cx]+1
                    q.append((target_y, target_x))

if distant[DY][DX] == 10**10:
    print(-1)
else:
    print(distant[DY][DX])