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

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
sum = 0
K = int(input())
for i in range(1,K+1):
  for j in range(1,K+1):
      for k in range(1,K+1):
        sum += gcd(i,j,k)

print(sum)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)
sum = 0
K = int(input())
for i in range(1,K+1):
  for j in range(1,K+1):
    gcd_0 = gcd(i,j)
    for k in range(1,K+1):
      sum += gcd(gcd_0,k)

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

import os
import sys
from collections import defaultdict, deque
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

graph = [[] for _ in range(N ** 2)]
ins = [0] * (N ** 2)
for i in range(N):
    for j in range(N - 2):
        a, b = i, A[i][j] - 1
        c, d = i, A[i][j + 1] - 1

        if a > b:
            a, b = b, a
        if c > d:
            c, d = d, c

        graph[a * N + b].append(c * N + d)
        ins[c * N + d] += 1

zeros = []
seen = []
for v, cnt in enumerate(ins):
    if cnt == 0:
        zeros.append(v)
        seen.append(v)

ans = 0
while zeros:
    nz = []
    for v in zeros:
        for u in graph[v]:
            ins[u] -= 1
            if ins[u] == 0:
                nz.append(u)
                seen.append(u)
    zeros = nz
    ans += 1
if len(seen) == len(graph):
    print(ans)
else:
    print(-1)


### FIXED CODE ###

import os
import sys
from collections import defaultdict, deque
from functools import lru_cache

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
A = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

graph = [[] for _ in range(N ** 2)]
ins = [0] * (N ** 2)
for i in range(N):
    for j in range(N - 2):
        a, b = i, A[i][j] - 1
        c, d = i, A[i][j + 1] - 1

        if a > b:
            a, b = b, a
        if c > d:
            c, d = d, c

        graph[a * N + b].append(c * N + d)
        ins[c * N + d] += 1

zeros = []
seen = []
for v, cnt in enumerate(ins):
    if cnt == 0:
        zeros.append(v)
        seen.append(v)

ans = 0
while zeros:
    nz = []
    for v in zeros:
        for u in graph[v]:
            ins[u] -= 1
            if ins[u] == 0:
                nz.append(u)
                seen.append(u)
    zeros = nz
    ans += 1
if len(seen) == len(graph):
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

s = input()
k = int(input())

s1 = []
for i in range(len(s)):
    for j in range(i + 1, len(s) + 1):
        s1.append(s[i:j])
s2 = []
for i in range(len(s1)):
    if len(s1[i]) <= 5:
        s2.append(s1[i])
s2.sort()
substring = []
i = 0
while len(substring) <= 4:
    try:
        if s2[i] not in substring:
            substring.append(s2[i])
        i = i + 1
    except:
        break
print(substring[k - 1])

### FIXED CODE ###

s = input()
k = int(input())

s1 = []
for i in range(len(s)):
    for j in range(i + 1, i + k + 1):
        s1.append(s[i:j])
s1.sort()
substring = []
i = 0
while len(substring) <= 4:
    try:
        if s1[i] not in substring:
            substring.append(s1[i])
        i = i + 1
    except:
        break
print(substring[k - 1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-

# AtCoder Grand Contest
# Problem A


if __name__ == '__main__':
    x = input()

    while 'ST' in x:
        x = x.replace('ST', '')

    print(len(x))


### FIXED CODE ###

# -*- coding: utf-8 -*-

# AtCoder Grand Contest
# Problem A


if __name__ == '__main__':
    from collections import deque

    x = input()
    n = len(x)
    d = deque()

    for i in range(n):
        d.append(x[i])

        if len(d) >= 2 and d[-2] + d[-1] == 'ST':
            d.pop()
            d.pop()

    print(len(d))
### BUGGY CODE ###

n, ma, mb = map(int, input().split())
U = 400
dp = [[[float("inf")]*(U+1) for _ in range(U+1)] for i in range(n+1)]
dp[0][0][0] = 0
for i in range(n):
  a, b, c = map(int, input().split())
  for j in range(U+1):
    for k in range(U+1):
      if j<a or k<b:
        dp[i+1][j][k] = dp[i][j][k]
      else:
        dp[i+1][j][k] = min(dp[i][j][k], dp[i][j-a][k-b]+c)
ans = float("inf")
for i in range(1, 1+U//max(ma, mb)):
  na, nb = i*ma, i*mb
  ans = min(ans, dp[-1][na][nb])
if ans == float("inf"):
  print(-1)
else:
  print(ans)

### FIXED CODE ###

n, ma, mb = map(int, input().split())
U = 400
dp = [[[float("inf")]*(U+1) for _ in range(U+1)] for i in range(n+1)]
dp[0][0][0] = 0
for i in range(n):
  a, b, c = map(int, input().split())
  for j in range(U+1):
    for k in range(U+1):
      if j<a or k<b:
        dp[i+1][j][k] = dp[i][j][k]
      else:
        dp[i+1][j][k] = min(dp[i][j][k], dp[i][j-a][k-b]+c)
ans = float("inf")
for i in range(1, 1+U//max(ma, mb)):
  na, nb = i*ma, i*mb
  ans = min(ans, dp[-1][na][nb])
if ans == float("inf"):
  print(-1)
else:
  print(ans)
### BUGGY CODE ###

N,M = map(int,input().split())
for i in range(N,M+1):
    if M%i==0:
        print(M//i)
        break

### FIXED CODE ###

N,M = map(int,input().split())
A = []
for i in range(1,M+1):
    if i*i>M:break
    if M%i==0:
        A.append(i)
        A.append(M//i)
A.sort()
for a in A:
    if a>=N:
        print(M//a)
        break
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10 ** 7)
N,Q =  map(int,input().split())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

val = [0 for i in range(N)]
for i in range(Q):
    a,b = map(int,input().split())
    val[a-1] += b 

def dps(i,parent): 
    for j in graph[i]:
        if j == parent:
            continue
        val[j] += val[i]
        dps(j,i)
                
dps(0,0)
print(*val[0:])

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)
readline = sys.stdin.readline
N,Q =  map(int,input().split())
graph = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,readline().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

val = [0 for i in range(N)]
for i in range(Q):
    a,b = map(int,readline().split())
    val[a-1] += b 

def dps(i,parent): 
    for j in graph[i]:
        if j == parent:
            continue
        val[j] += val[i]
        dps(j,i)
                
dps(0,-1)
print(*val)
### BUGGY CODE ###

import math


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

A.sort()

R = 0
M = []

if len(A) == 2:
    print(A[1], A[0])
else:
    for i in range(n):
        a = A[n-1-i]
        k = a / 2
        B = []
        C = []
        if R > math.factorial(a) // (math.factorial(a-math.ceil(a/2)) ** 2):
            break
        for j in range(n):
            if A[j] < k:
                B.append(A[j])
            else:
                C.append(A[j])
                break
        b = B[-1]
        c = C[0]
        r_b = math.factorial(a) // (math.factorial(a-b) * math.factorial(b))
        r_c = math.factorial(a) // (math.factorial(a-c) * math.factorial(c))
        if r_b >= r_c and r_b > R:
            M = [a, b]
            R = r_b
        elif r_c >= r_b and r_c > R:
            M = [a, c]
            R = r_c

    print(M[0], M[1])


### FIXED CODE ###

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

A.sort()

if len(A) == 2:
    print(A[1], A[0])
else:
    a = A[-1]
    k = a / 2
    B = [a for a in A if a <  k]
    C = [a for a in A if a >= k]

    if k - B[-1] > C[0] - k:
        print(a, C[0])
    else:
        print(a, B[-1])
### BUGGY CODE ###

#coding: utf-8

n, q = map(int, raw_input().split())
s = raw_input()
for i in range(q):
    a, b = map(int, raw_input().split())
    print(s[a-1:b].count("AC"))


### FIXED CODE ###

#coding: utf-8
import bisect

n, q = map(int, raw_input().split())
s = raw_input()
i_list = []
i = -1
while True:
    i = s.find("AC", i+1)
    if(i == -1): break
    i_list.append(i)
for i in range(q):
    a, b = map(int, raw_input().split())
    a = bisect.bisect_left(i_list, a-1)
    b = bisect.bisect_left(i_list, b-1)
    print(b-a)
### BUGGY CODE ###

N, Q = map(int,input().split())
S = input()
qlist = [list(map(int, input().split())) for _ in range(Q)]

for q in qlist:
    sparts = S[q[0]-1:q[1]]
    print(sparts.count("AC"))


### FIXED CODE ###

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


cnt = [0] * (N)

for i in range(1, N):
	if S[i-1:i+1] == "AC":
		cnt[i] = cnt[i-1] + 1
	else:
		cnt[i] = cnt[i-1]

for _ in range(Q):
	l, r = map(int, input().split())
	print(cnt[r-1] - cnt[l-1])
### BUGGY CODE ###

import math
A, B, N = map(int,input().split(' '))

def f(x):
    return math.floor(A*x/B)-A*math.floor(x/B)


def main():
    
    ans = 0
    i = 0
    while B > i and i <= N:
        fi = f(i)
        ans = f(i) if ans < fi else ans
        i += 1 
    
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

import math
A, B, N = map(int,input().split(' '))

def f(x):
    return math.floor(A*x/B)-A*math.floor(x/B)


def main():
    if N >= B:
        print(f(B-1))
    else:
        print(f(N))

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

N, M = list(map(int, input().split()))
for n in range(N,M+1):
    if M%n==0:
        print(M//n)
        break

### FIXED CODE ###

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

f1, f2 = [], []

k = 1
while k*k<=M:
    if M%k==0:
        f1.append(k)
        f2.append(M//k)
    k+=1

for f in f1 + list(reversed(f2)):
    if f>=N:
        print(M//f)
        break
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0

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


### FIXED CODE ###

N = int(input())
S = input()
ans = S.count("R") * S.count("G") * S.count("B")


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

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

import math
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def myinput():
    return map(int,readline().split())

n = int(readline())
a = list(myinput())
mod = 10**9 + 7
ans = 0

if max(a)==0:
  print(0)
  exit()

m = math.floor(math.log(max(a),2))+1

for j in range(m):
    one = 0
    zero = 0
    for i in range(n):
        b = str(bin(a[i]))[2:]
        c = b.zfill(m)
        s = int(c[m-j-1])
        if s==0:
            zero += 1
        else:
            one += 1
    ans_bit = zero * one
    ans += (ans_bit)*(2**j) 
    ans %= mod

print(ans%mod)

### FIXED CODE ###

import math
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def myinput():
    return map(int,readline().split())

n = int(readline())
a = list(myinput())
mod = 10**9 + 7
ans = 0

for j in range(60):
    k = 2**j
    one = 0
    zero = 0
    for i in range(n):
        if (a[i]&k):
            one += 1
        else:
            zero += 1
    ans_bit = zero * one
    ans += (ans_bit)*(2**j) 
    ans %= mod   

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

import sys
sys.setrecursionlimit(10**6)
mod = 10**9+7
p2 = [1]*(3*10**5)
for n in range(3*10**5-1):
    p2[n+1] = p2[n]*2%mod

N = int(input())
AB = [list(map(int,input().split())) for _ in range(N-1)]
g = [[] for _ in range(N+1)]
for i in range(N-1):
    a,b = AB[i]
    g[a].append(b)
    g[b].append(a)

l1 = [0]*(N+1)
l2 = [[] for _ in range(N+1)]

def rec(p,c):
    res = 0
    for a in g[c]:
        if a == p:
            continue
        n = rec(c,a)
        l2[c].append(n+1)
        res += n+1
    l1[c] = res
    return res

n = rec(0,1)
for i in range(1,N+1):
    l2[i].append(N-1-l1[i])

ans = 0
for i in range(1,N+1):
    ans += p2[N-1]-1
    ans %= mod
    for j in l2[i]:
        ans -= p2[j]-1
        ans %= mod
ans *= pow(p2[N],mod-2,mod)
ans %= mod
print(ans)


### FIXED CODE ###

from collections import defaultdict,deque
mod = 10**9+7
N = int(input())
g = [[] for _ in range(N)]
d = defaultdict(lambda:-1)
p2 = [1]*(N+1)
p2[1] = pow(2,mod-2,mod)
for i in range(N):
    p2[i+1] = (p2[i]*p2[1])%mod

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

q = deque([[a,b]])
while q:
    i,j = q.pop()
    s = 1
    f = True
    for k in g[j]:
        if k == i:
            continue
        if (j,k) not in d:
            if f:
                q.append([i,j])
            q.append([j,k])
            f = False
        else:
            s += d[(j,k)]
    if f:
        d[(i,j)] = s

q = deque([[b,a]])
while q:
    i,j = q.pop()
    s = 1
    f = True
    for k in g[j]:
        if k == i:
            continue
        if (j,k) not in d:
            if f:
                q.append([i,j])
            q.append([j,k])
            f = False
        else:
            s += d[(j,k)]
    if f:
        d[(i,j)] = s

ans = 1-p2[N]-N*p2[1]

for i in range(N):
    for j in g[i]:
        if j<i:
            continue
        n = max(d[(i,j)],d[(j,i)])
        ans += (1-p2[n])*(1-p2[N-n])
        ans %= mod

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

l,r = map(int, input().split())

min = 2019
diff = r-l+1

for i in range(diff):
  for j in range(diff):
    if j > i:
      total = (i+l)*(j+l)
      if total > 2019:
        mod = total % 2019
        if min > mod:
           min = mod
      else:
        if min > total:
          min = total
print(min)

### FIXED CODE ###

l,r = map(int, input().split())

min = 2019
diff = r-l+1

if diff > 2019:
  diff = 2019

for i in range(diff):
  for j in range(diff):
    if j > i:
      total = (i+l)*(j+l)
      if total > 2019:
        mod = total % 2019
        if min > mod:
           min = mod
      else:
        if min > total:
          min = total
print(min)
### BUGGY CODE ###

from heapq import heappop, heappush

H, W, K = map(int, input().split())
x1, y1, x2, y2 = map(int, input().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1

C = [input() for i in range(H)]
dist = {}
d = [[0, x1, y1, K, -1]]
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  cost, x, y, remain, v = heappop(d)
  if (x, y, v%2) in dist:
    continue
  dist[(x, y, v%2)] = cost
  for i, (dx, dy) in enumerate(dxy):
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W and C[xx][yy] != '@':
      if (xx, yy, i%2) in dist:
        continue
      if i == v and remain:
        heappush(d, [cost, xx, yy, remain-1, i])
      else:
        heappush(d, [cost+1, xx, yy, K-1, i])

cands = [dist[(x2, y2, i)] for i in range(2) if (x2, y2, i) in dist]
if cands:
  print(min(cands))
else:
  print(-1)

### FIXED CODE ###

import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
from collections import deque
 
H, W, K = map(int,readline().split())
x1, y1, x2, y2 = map(int,readline().split())
x1 -= 1; y1 -= 1; x2 -= 1; y2 -= 1
C = read().split()

dist = [[-1]*W for i in range(H)]
dist[x1][y1] = 0
d = deque([[x1, y1]])
dxy= [[1, 0], [0, 1], [-1, 0], [0, -1]]
while d:
  x, y = d.popleft()
  if (x, y) == (x2, y2):
    print(dist[x][y])
    quit()
  for dx, dy in dxy:
    xx = x; yy = y
    for i in range(K):
      xx += dx; yy += dy
      if 0<=xx<H and 0<=yy<W and C[xx][yy]!='@':
        if 0 <= dist[xx][yy] <= dist[x][y]:
          break
        if dist[xx][yy] == -1:
           d.append([xx, yy])
        dist[xx][yy] = dist[x][y] + 1
      else:
        break

print(-1)
### BUGGY CODE ###

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

for i in range(n):
    b = [0] + a[:i] + a[i+1:] + [0]
    ans = 0
    for j in range(len(b)-1):
        ans += abs(b[j] - b[j+1])
    print(ans)

### FIXED CODE ###

n = int(input())
a = [0] + list(map(int, input().split())) + [0]
cost = 0
for i in range(n+1):
    cost += abs(a[i] - a[i+1])
    
for j in range(1, n+1):
    if a[j-1] <= a[j] <= a[j+1] or a[j-1] >= a[j] >= a[j+1]:
        print(cost)
    else:
        print(cost - min(abs(a[j] - a[j-1]), abs(a[j] - a[j+1]))*2)
### BUGGY CODE ###

S = list(input())
Q = int(input())

for i in range(Q):
    que = input()
    if que == "1":
        S.reverse()
    else:
        j, F, C = que.split()
        if int(F) == 1:
            S = [C] + S
        else:
            S = S + [C]

for s in S:
    print(s, end="")

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())

Sq = deque(S)


flg = True
for i in range(Q):
    que = input()
    if que == "1":
        if flg:
            flg = False
        else:
            flg = True
    else:
        j, F, C = que.split()
        if int(F) == 1:
            if flg:
                Sq.appendleft(C)
            else:
                Sq.append(C)
        else:
            if flg:
                Sq.append(C)
            else:
                Sq.appendleft(C)

if flg:
    for i in Sq:
        print(i, end="")
else:
    Sq.reverse()
    for i in Sq:
        print(i, end="")
### BUGGY CODE ###

def gcd(a, b, c):
    r = 1
    if a == 1 or b == 1 or c == 1:
        return 1
    for i in range(min(a, b, c) + 1):
        i += 1
        if a % i == 0 and b % i == 0 and c % i == 0:
            r = i
    return r

v = int(input())
sum = 0

for i in range(v):
    i += 1
    for j in range(v):
        j += 1
        for k in range(v):
            k += 1
            sum += gcd(i, j, k)

print(sum)

### FIXED CODE ###

from math import gcd

v = int(input())
sum = 0

for i in range(1, v + 1):
    for j in range(1, v + 1):
        for k in range(1, v + 1):
            sum += gcd(gcd(i, j), k)

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

N = int(input())
A = list(map(int,input().split()))
cnt = []
for j in range(1,N+1):
    print(A.count(j))



### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
cnt = [0]*N

for a in A:
    cnt[a-1] += 1
print('\n'.join(map(str,cnt)))
#count()ではTLE
### BUGGY CODE ###

from functools import reduce
from math import gcd

K = int(input())

count = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        for k in range(1, K+1):
            a = [i, j, k]
            count += reduce(gcd, a)
print(count)


### FIXED CODE ###

from math import gcd

K = int(input())

count = 0

for i in range(1, K+1):
    for j in range(1, K+1):
        a = gcd(i, j)
        for k in range(1, K+1):
            count += gcd(a, k)
print(count)
### BUGGY CODE ###

import math
import sys
import collections

def main():
    N=int(input())
    Tr=tuple(input())
    R=[]
    G=[]
    B=[]
    for i in range(N):
       if Tr[i]=="R":
           R.append(i)
           continue
       if Tr[i]=="G":
           G.append(i)
           continue
       if Tr[i]=="B":
           B.append(i)
           continue
    cnt=len(R)*len(G)*len(B)
    for i in R:
        for j in G:
            if max(i,j)+abs(i-j) in B:
                cnt-=1
            if min(i,j)-abs(i-j) in B:
                cnt-=1
            if (i+j)%2==0 and (i+j)//2 in B:
                cnt-=1
    print(cnt)
if __name__ == '__main__':
    main()

### FIXED CODE ###

import math
import sys
import collections

def main():
    N=int(input())
    Tr=list(input())
    R=[]
    G=[]
    B=[]
    for i in range(N):
       if Tr[i]=="R":
           R.append(i)
           continue
       if Tr[i]=="G":
           G.append(i)
           continue
       if Tr[i]=="B":
           B.append(i)
           continue
    cnt=len(R)*len(G)*len(B)
    for j in range(N):
        for i in range(j):
            if 2*j-i<=N-1:
                if Tr[2*j-i]!=Tr[i] and Tr[2*j-i]!=Tr[j] and Tr[j]!=Tr[i]:
                    cnt-=1
    print(cnt)
if __name__ == '__main__':
    main()
### BUGGY CODE ###

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

b = []
for i in range(n):
    r = 0
    for j in range(n-i):
        r += a[i+j]
        b.append(r)


n2 = len(b)

res = 0
for i in range(41):
    p = res + (1 << (40-i))
    
    c = 0
    for j in range(n2):
        if p == p&b[j]:
            c+=1
    
    if c >= k:
        res = p

print(res)

### FIXED CODE ###

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

b = []
for i in range(n):
    r = 0
    for j in range(i,n):
        r += a[j]
        b.append(r)


n2 = n*(n+1)//2

res = 0
for i in range(41):
    p = res + 2**(40-i)
    
    c = 0
    for j in range(n2):
        if p == p&b[j]:
            c+=1
    
    if c >= k:
        res = p

print(res)
### BUGGY CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
loop_flags = [False] * N
loops = []
for i in range(N):
    if loop_flags[i]:
        continue
    next_cell = i
    loop = []
    while not loop_flags[next_cell]:
        loop_flags[next_cell] = True
        loop.append(C[next_cell])
        next_cell = P[next_cell] - 1
    if loop:
        loops.append(loop)
# print(loops)
ans = C[0]
for loop in loops:
    work_loop_sum = []
    now = 0
    tmp_ans = 0
    one_loop_point = sum(loop)
    if one_loop_point <= 0 or K <= len(loop):
        for i in range(1, K + 1):
            tmp_ans = sum(loop[:i])
            for j in range(len(loop)):
                ans = max(tmp_ans, ans)
                tmp_ans = tmp_ans - loop[j] + loop[(i + j) % len(loop)]
    else:
        for i in range(min(K + 1, len(loop) + 1)):
            tmp_ans = sum(loop[:i]) + ((K - i) // len(loop)) * one_loop_point
            for j in range(len(loop)):
                ans = max(tmp_ans, ans)
                tmp_ans = tmp_ans - loop[j] + loop[(i + j) % len(loop)]

print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
loop_flags = [False] * N
loops = []
for i in range(N):
    if loop_flags[i]:
        continue
    next_cell = i
    loop = []
    while not loop_flags[next_cell]:
        loop_flags[next_cell] = True
        loop.append(C[next_cell])
        next_cell = P[next_cell] - 1
    if loop:
        loops.append(loop)
# print(loops)
ans = C[0]
for loop in loops:
    work_loop_sum = []
    now = 0
    tmp_ans = 0
    one_loop_point = sum(loop)
    if one_loop_point <= 0 or K <= len(loop):
        for i in range(1, min(K + 1, len(loop) + 1)):
            tmp_ans = sum(loop[:i])
            for j in range(len(loop)):
                ans = max(tmp_ans, ans)
                tmp_ans = tmp_ans - loop[j] + loop[(i + j) % len(loop)]
    else:
        for i in range(min(K + 1, len(loop) + 1)):
            tmp_ans = sum(loop[:i]) + ((K - i) // len(loop)) * one_loop_point
            for j in range(len(loop)):
                ans = max(tmp_ans, ans)
                tmp_ans = tmp_ans - loop[j] + loop[(i + j) % len(loop)]

print(ans)