CodeEff/ECCO huggingface dataset:
# Original solution
import sys
from collections import deque

N, K = list(map(int, sys.stdin.readline().split()))
P = list(map(int, sys.stdin.readline().split()))
C = list(map(int, sys.stdin.readline().split()))

# 重み付き有向グラフ
# edges = [[] for _ in range(N)]
# for i in range(N):
#     edges[i].append((P[i]-1, C[i]))

# DFSで閉路と経路の最大取得スコアを調査
ans = -float("inf")
for i in range(N):
    q = deque([(i, 0, 0)])
    cycle_score = -1
    cycle_count = -1
    cycle_start = None
    scores = {} # (score, count)
    while q:
        node1, score, count = q.popleft()
        # print(node1, score, count)
        if K < count:
            break
        if 0 < count: 
            ans = max(ans, score)
        if node1 in scores:
            # 閉路
            if score > 0:
                # print("plus cycle detected")
                # cycle.add((score, count, i))
                cycle_score = score
                cycle_count = count
                cycle_start = node1
            break
        scores[node1] = (score, count)
        # for で回しているが、実際は一択
        # for node2, weight in edges[node1]:
        #     q.appendleft((node2, score + weight, count + 1))
        node2 = P[node1] - 1
        weight = C[node2]
        q.append((node2, score + weight, count + 1))

    # cycleを回れる限界の-1から始めて、最大のスコアを算出
    if cycle_start is not None:
        cycle_len = cycle_count - scores[cycle_start][1]
        # print("cycle_len", cycle_len, "cycle_score", cycle_score - scores[cycle_start][0])
        loop = (K - scores[cycle_start][1]) // cycle_len - 1

        count = loop * cycle_len + scores[cycle_start][1]
        score = scores[cycle_start][0] + loop * (cycle_score - scores[cycle_start][0])
        # print(count, score, loop)
        q = deque([(cycle_start, score, count)])
        while q:
            node1, score, count = q.popleft()
            # print(node1, score, count)
            if count > K:
                break

            ans = max(ans, score)
            # for node2, weight in edges[node1]:
            #     q.appendleft((node2, score + weight, count + 1))
            node2 = P[node1] - 1
            weight = C[node2]
            q.append((node2, score + weight, count + 1))

print(ans)

# Optimized solution
import sys

input = sys.stdin.readline
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
C = list(map(int, input().split()))
 
ans = -float('inf')
for s in range(N):
    S = [] 
    i = P[s] - 1
    S.append(C[i])
    while i != s:
        i = P[i] - 1
        S.append(S[-1] + C[i])
 
    if K <= len(S):
        tmp = max(S[:K])
    elif S[-1] <= 0:
        tmp = max(S)
    else:
        # ループの中で最大となるところで止める
        tmp1 = S[-1] * (K // len(S) - 1)
        tmp1 += max(S)
        # 限界まで進む
        tmp2 = S[-1] * (K // len(S))
        r = K % len(S)
        if r != 0:
            tmp2 += max(0, max(S[:r]))
        tmp = max(tmp1, tmp2)
 
    ans = max(ans, tmp)
 
print(ans)
# Original solution
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N, K = list(map(int, input().split()))
P = list([int(x) - 1 for x in input().split()])
C = list(map(int, input().split()))


ans = -INF
for i in range(N):
    nx = i
    total = 0
    L = [] 
    while True:
        nx = P[nx]
        total += C[nx]
        L.append(C[nx])
        if nx == i:
            break
    l = len(L)
    now = 0
    for j in range(l):
        if j + 1 > K:
            break
        now += L[j]
        ans = max(ans, now)
    if total > 0:
        now = total * (K // l)
        ans = max(ans, now)
        r = K % l
        for j in range(r):
            now += L[j]
            ans = max(ans, now)
print(ans)




# Optimized solution
import sys
import itertools
# import numpy as np
import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

# map(int, input().split())

N, K = list(map(int, input().split()))
P = list([int(x) - 1 for x in input().split()])
C = list(map(int, input().split()))


ans = -INF
for i in range(N):
    nx = i
    total = 0
    L = [] 
    while True:
        nx = P[nx]
        total += C[nx]
        L.append(C[nx])
        if nx == i:
            break
    l = len(L)
    tmp = 0
    for j in range(l):
        if j + 1 > K:
            break
        tmp += L[j]
        now = tmp
        if total > 0:
            e = (K - j - 1) // l
            now += total * e
        ans = max(ans, now)
    # if total > 0:
    #     now = total * (K // l)
    #     ans = max(ans, now)
    #     r = K % l
    #     for j in range(r):
    #         now += L[j]
    #         ans = max(ans, now)
print(ans)
# Original solution
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import accumulate
from collections import deque, defaultdict
def main():
    n, ko = list(map(int, input().split()))
    p = tuple(map(int, input().split()))
    c = tuple(map(int, input().split()))

    scores_all = deque()
    for k1 in range(n):
        scores = deque()
        kita = defaultdict(int)
        kita[k1] = ko
        cnt = ko - 1
        koko = p[k1] - 1
        scores.append(c[koko])
        kita[koko] = cnt
        while cnt:
            cnt -= 1
            koko = p[koko] - 1
            scores.append(c[koko])
            if kita[koko]:
                break
            else:
                kita[koko] = cnt
        cycle_long = kita[koko] - cnt
        scores_a = tuple(accumulate(scores))

        if cnt:
            if scores_a[-1] > 0:
                kaisuu = ko // cycle_long
                s1 = scores_a[-1] * kaisuu
                amari = ko % cycle_long
                if amari:
                    t = max(0, max(scores_a[:amari]))
                    s1 += t
                s2 = scores_a[-1] * (kaisuu - 1)
                s2 += max(scores_a)
                scores_all.append(max(s1, s2))
            else:
                scores_all.append(max(scores_a))
        else:
            scores_all.append(max(scores_a))
    print((max(scores_all)))

if __name__ == '__main__':
    main()

# Optimized solution
import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
from itertools import accumulate
def main():
    n, k = list(map(int, input().split()))
    p = tuple(map(int, input().split()))
    c = tuple(map(int, input().split()))

    if k == 1:
        print((max(c)))
        sys.exit()
    seen = [0] * n
    cycles = []
    for i1 in range(n):
        if not seen[i1]:
            cycle_t = []
            koko = i1
            while True:
                if seen[koko]:
                    cycles.append(cycle_t)
                    break
                cycle_t.append(c[koko])
                seen[koko] = 1
                koko = p[koko] - 1

    score = max(c)
    for cycle in cycles:
        score_t = max(cycle)
        cycle_len = len(cycle)
        cycle_sum = sum(cycle)
        kaisu, rem = divmod(k, cycle_len)
        if rem == 0:
            kaisu -= 1
            rem = cycle_len
        if kaisu > 0:
            kaisu -= 1
            rem += cycle_len
        cycle = tuple(accumulate(cycle + cycle + cycle))
        for i1 in range(2, rem + 1):
            for i2 in range(cycle_len):
                score_t = max(score_t, cycle[i1+i2] - cycle[i2])
        if cycle_sum > 0:
            score_t += (kaisu * cycle_sum)
        score = max(score, score_t)
    print(score)

if __name__ == '__main__':
    main()
# Original solution
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, K = [int(x) for x in input().split()]
    P = [int(x) for x in input().split()]
    C = [int(x) for x in input().split()]

    ans = -float("inf")
    for i in range(N):
        next = P[i] - 1
        cnt = 0
        tmp = 0

        f = False
        while True:
            tmp += C[next]
            ans = max(ans, tmp)
            cnt += 1
            if next == i:
                break
            if cnt == K or next == i:
                f = True
                break
            next = P[next] - 1

        if f or tmp <= 0:
            continue

        q, r = divmod(K, cnt)
        next = P[i] - 1
        tmp *= q
        cnt = 0
        while True:
            tmp += C[next]
            ans = max(ans, tmp)
            cnt += 1
            if cnt == r:
                break
            next = P[next] - 1
    print(ans)


if __name__ == '__main__':
    main()


# Optimized solution
import sys

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, K = [int(x) for x in input().split()]
    P = [int(x) - 1 for x in input().split()]
    C = [int(x) for x in input().split()]

    ans = max(C)
    for i in range(N):
        next = P[i]
        cnt = 0
        tmp = 0

        while True:
            tmp += C[next]
            ans = max(ans, tmp)
            cnt += 1
            if cnt == K or next == i:
                break
            next = P[next]

        if cnt == K or tmp <= 0:
            continue

        q = K // cnt
        r = K % cnt
        next = P[i]
        if q != 0:
            tmp *= (q - 1)
            q -= 1
            r += cnt
            ans = max(ans, tmp)
        else:
            tmp = 0
        while r > 0:
            tmp += C[next]
            ans = max(ans, tmp)
            next = P[next]
            r -= 1
    print(ans)


if __name__ == '__main__':
    main()
# Original solution
N, K = list(map(int,input().split()))
P = [int(x)-1 for x in input().split()]
C = [int(x) for x in input().split()]

def loop(s):
    value = 0
    done = set()
    while s not in done:
        done.add(s)
        s = P[s]
        value += C[s]
    return len(done), value

def f(s,K):
    ans = -10**18
    total = 0
    done = set()
    while s not in done:
        done.add(s)
        s = P[s]
        total += C[s]
        ans = max(ans,total)
        K -= 1

        if K==0:
            return ans

    lamb, value = loop(s)

    if K > 2*lamb:
        K -= lamb
        if value > 0:
            total += (K//lamb)*value
            ans = max(ans,total)
            K -= (K//lamb)*lamb
        K += lamb

    while K > 0:
        s = P[s]
        total += C[s]
        ans = max(ans,total)
        K -= 1
    return ans

print((max([f(s,K) for s in range(N)])))

# Optimized solution
N, K = list(map(int,input().split()))
P = [int(x)-1 for x in input().split()]
C = [int(x) for x in input().split()]

def loop(s):
    value = 0
    done = set()
    while s not in done:
        done.add(s)
        s = P[s]
        value += C[s]
    return len(done), value

def f(s,K):
    ans = -10**18
    total = 0
    done = set()
    while s not in done:
        done.add(s)
        s = P[s]
        total += C[s]
        ans = max(ans,total)
        K -= 1

        if K==0:
            return ans

    lamb, value = loop(s)

    if K > 2*lamb:
        if value > 0:
            K -= lamb
            total += (K//lamb)*value
            ans = max(ans,total)
            K -= (K//lamb)*lamb
            K += lamb
    if value <= 0:
        K = min(K,lamb+5)
        


    while K > 0:
        s = P[s]
        total += C[s]
        ans = max(ans,total)
        K -= 1
    return ans

print((max([f(s,K) for s in range(N)])))
# Original solution
INF=10**9
f=lambda:[*list(map(int,input().split()))]
n,k=f()
p,c=f(),f()
p=[*[x-1 for x in p]]
tp=[[*list(range(n))] for _ in range(n+1)]
tc=[[0]*n for _ in range(n+1)]
lt=[0]*n
lc=[0]*n
for i in range(n):
  for j in range(n):
    t=p[tp[i][j]]
    tp[i+1][j]=t
    tc[i+1][j]=tc[i][j]+c[t]
    if t==j and lt[j]==0:
      lt[j]=i+1
      lc[j]=tc[i+1][j]
a=-INF
for i in range(n):
  if lc[i]<1 or k<=lt[i]:
    for j in range(min(lt[i],k)):
      a=max(a,tc[j+1][i])
  else:
    for j in range(lt[i]):
      t=k//lt[i]*lc[i]+tc[j+1][i]
      if k%lt[i]<j+1: t-=lc[i]
      a=max(a,t)
print(a)

# Optimized solution
f=lambda:[*list(map(int,input().split()))]
n,k=f()
p,c=f(),f()
p=[*[x-1 for x in p]]
a=-10**9
for i in range(n):
  x=i
  l=[]
  s=0
  while 1:
    x=p[x]
    l+=[c[x]]
    s+=c[x]
    if x==i: break
  m=len(l)
  t=0
  for j in range(m):
    if j+1>k: break
    t+=l[j]
    a=max(a,t+(k-j-1)//m*s*(s>0))
print(a)
# Original solution
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
C = list(map(int, input().split()))

P = [None] + P
C = [None] + C

all_max = C[1]
for st in range(1, N + 1):
    scores = []
    visit = set()
    p = st

    while p not in visit and len(visit) < K:
        next_p = P[p]
        scores.append(C[next_p])
        visit.add(p)
        p = next_p

    num_elem = len(scores)
    all_sum = sum(scores)

    q, r = divmod(K, num_elem)

    max_ = scores[0]
    temp = scores[0]

    max_r = scores[0]
    temp_r = scores[0]
    for x in range(1, num_elem):
        if x < r:
            temp_r += scores[x]
            max_r = max(max_r, temp_r)

        temp += scores[x]
        max_ = max(max_, temp)

    temp_max = scores[0]
    if all_sum > 0 and q > 0:
        if r > 0:
            temp_max = max(all_sum * (q - 1) + max_, all_sum * q + max_r)
        else:
            temp_max = all_sum * (q - 1) + max_
    else:
        temp_max = max_

    all_max = max(all_max, temp_max)


print(all_max)


# Optimized solution
N, K = list(map(int, input().split()))
P = list(map(int, input().split()))
C = list(map(int, input().split()))

P = [None] + P
C = [None] + C

all_max = C[1]
for st in range(1, N + 1):
    p = P[st]
    scores = [C[p]]

    while p != st and len(scores) < K:
        p = P[p]
        scores.append(C[p])

    num_elem = len(scores)
    all_sum = sum(scores)

    q, r = divmod(K, num_elem)

    max_ = scores[0]
    temp = scores[0]

    max_r = scores[0]
    temp_r = scores[0]
    for x in range(1, num_elem):
        if x < r:
            temp_r += scores[x]
            max_r = max(max_r, temp_r)

        temp += scores[x]
        max_ = max(max_, temp)

    temp_max = scores[0]
    if all_sum > 0 and q > 0:
        if r > 0:
            temp_max = max(all_sum * (q - 1) + max_, all_sum * q + max_r)
        else:
            temp_max = all_sum * (q - 1) + max_
    else:
        temp_max = max_

    all_max = max(all_max, temp_max)


print(all_max)
# Original solution
n,k = list(map(int,input().split()))
p = list(map(int,input().split()))
for i in range(n):
    p[i] -= 1
c = list(map(int,input().split()))

reach = [False]*n
x = []
for i in range(n):
    if reach[i]:continue
    buf = []
    cur = i
    while not reach[cur]:
        buf.append(c[cur])
        reach[cur] = True
        cur = p[cur]
    x.append(buf)

ans = max(c)
import itertools
for i in x:
    n = k//len(i)
    ind = k%len(i)
    if n>0:
        n -= 1
        ind += len(i)
    else:
        ind = min(k,len(i)*2)
    ii = i+i+i
    r = list(itertools.accumulate(ii))
    a = max(0,r[len(i)-1]*n)
    for j in range(len(i)):
        for z in range(1,ind+1):
            s = r[j+z]-r[j]
            if z<ind+1:ans = max(ans,a+s)
            else:ans = max(ans,s)
print(ans)


# Optimized solution
n,k = list(map(int,input().split()))
p = list(map(int,input().split()))
for i in range(n):
    p[i] -= 1
c = list(map(int,input().split()))

reach = [False]*n
x = []
for i in range(n):
    if reach[i]:continue
    buf = []
    cur = i
    while not reach[cur]:
        buf.append(c[cur])
        reach[cur] = True
        cur = p[cur]
    x.append(buf)

ans = max(c)
import itertools
for i in x:
    n = k//len(i)
    ind = k%len(i)
    if n>0:
        n -= 1
        ind += len(i)
    else:
        ind = min(k,len(i)*2)
    ii = i+i+i
    r = list(itertools.accumulate(ii))
    a = max(0,r[len(i)-1]*n)
    for j in range(len(i)):
        for z in range(1,ind+1):
            s = r[j+z]-r[j]
            ans = max(ans,a+s)
print(ans)
# Original solution
n, k = list(map(int, input().split()))
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

ans = - 10 ** 18
for i in range(1, n+1):
    base = i
    nxt = p[i]
    cnt = 0
    score = 0
    while True:
        cnt += 1
        if cnt > k:
            break
        score += c[nxt]
        ans = max(ans, score)
        #print("i = ", i, "ans = ", ans, "score = ", score)
        if nxt == base:
            break
        nxt = p[nxt]
    if cnt >= k:
        continue
    extra = k - cnt
    score_tmp = score
    nxt_tmp = nxt
    nxt = p[nxt]
    for j in range(extra):
        score += c[nxt]
        ans = max(ans, score)
        #print("ans = ", ans, "score = ", score, "nxt = ", nxt, "c[nxt] = ", c[nxt])
        nxt = p[nxt]
    score = score_tmp
    nxt = nxt_tmp
    a = extra // cnt
    score += score * a
    ans = max(ans, score)
    for j in range(extra - a * cnt):
        score += c[nxt]
        ans = max(ans, score)
        nxt = p[nxt]

print(ans)

# Optimized solution
n, k = list(map(int, input().split()))
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

ans = - 10 ** 18
for i in range(1, n+1):
    base = i
    nxt = p[i]
    cnt = 0
    score = 0
    while True:
        cnt += 1
        if cnt > k:
            break
        score += c[nxt]
        ans = max(ans, score)
        #print("i = ", i, "ans = ", ans, "score = ", score)
        if nxt == base:
            break
        nxt = p[nxt]
    if cnt >= k:
        continue
    extra = k - cnt
    score_tmp = score
    nxt = p[nxt]
    nxt_tmp = nxt
    for j in range(min(extra, cnt)):
        score += c[nxt]
        ans = max(ans, score)
        #print("ans = ", ans, "score = ", score, "nxt = ", nxt, "c[nxt] = ", c[nxt])
        nxt = p[nxt]
    #print("score = ", score, "ans = ", ans)
    score = score_tmp
    nxt = nxt_tmp
    a = extra // cnt
    if extra % cnt == 0:
        a -= 1
    score += score * max(a, 0)
    ans = max(ans, score)
    for j in range(extra - a * cnt):
        score += c[nxt]
        ans = max(ans, score)
        #print("ans = ", ans, "score = ", score, "nxt = ", nxt, "c[nxt] = ", c[nxt])
        nxt = p[nxt]

print(ans)
# Original solution
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
c = list(map(int, input().split()))

mv_array = [set() for _ in range(n)]
score_mv_array = [[] for _ in range(n)]
score_array = [0]*n

def get_sum(array):
    score_array = [0]
    for i, a in enumerate(array):
        score_array.append(score_array[i]+a)
    return max(score_array)

def get_max(array, q, mod):
    if q == 0:
        m_score = get_sum(array[:mod])
    else:
        m_score = get_sum(array+array[:mod])
        m_score = sum(array)*(q-1) + m_score
    return m_score

for i in range(n):
    score = 0
    max_score = c[i]
    pos = i
    for j in range(k):
        pos = p[pos]-1
        if pos in mv_array[i]:
            len_mv = len(score_mv_array[i])
            q, mod = divmod(k-j, len_mv)
            score += get_max(score_mv_array[i], q, mod)
            max_score = max(score, max_score)
            break
        score += c[pos]
        mv_array[i].add(pos)
        score_mv_array[i].append(c[pos])
        max_score = max(score, max_score)
    score_array[i] = max_score

print((max(score_array)))

# Optimized solution
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
c = list(map(int, input().split()))

# mv_array = [set() for _ in range(n)]
score_mv_array = [[] for _ in range(n)]
score_array = [0]*n

def get_sum(array):
    score_array = [0]
    for i, a in enumerate(array):
        score_array.append(score_array[i]+a)
    return max(score_array)

def get_max(array, q, mod):
    if q == 0:
        m_score = get_sum(array[:mod])
    else:
        m_score = get_sum(array+array[:mod])
        m_score = sum(array)*(q-1) + m_score
    return m_score

for i in range(n):
    score = 0
    max_score = c[i]
    pos = i
    start_pos = p[pos]-1
    for j in range(k):
        pos = p[pos]-1
        # if pos in mv_array[i]:
        if j!=0 and pos == start_pos:
            len_mv = len(score_mv_array[i])
            q, mod = divmod(k-j, len_mv)
            score += get_max(score_mv_array[i], q, mod)
            max_score = max(score, max_score)
            break
        score += c[pos]
        # mv_array[i].add(pos)
        score_mv_array[i].append(c[pos])
        max_score = max(score, max_score)
    score_array[i] = max_score

print((max(score_array)))
# Original solution
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
c = list(map(int, input().split()))

# mv_array = [set() for _ in range(n)]
# score_mv_array = [[] for _ in range(n)]
score_array = [0]*n

def get_sum(array):
    score_array = [0]
    for i, a in enumerate(array):
        score_array.append(score_array[i]+a)
    return max(score_array)

def get_max(array, q, mod):
    if q == 0:
        m_score = get_sum(array[:mod])
    else:
        m_score = get_sum(array+array[:mod])
        m_score = sum(array)*(q-1) + m_score
    return m_score

for i in range(n):
    score = 0
    max_score = c[i]
    score_mv_array = []
    pos = i
    start_pos = p[pos]-1
    for j in range(k):
        pos = p[pos]-1
        if j!=0 and pos == start_pos:
            # len_mv = len(score_mv_array)
            len_mv = j
            q, mod = divmod(k-j, len_mv)
            score += get_max(score_mv_array, q, mod)
            max_score = max(score, max_score)
            break
        score += c[pos]
        score_mv_array.append(c[pos])
        max_score = max(score, max_score)
    score_array[i] = max_score

print((max(score_array)))

# Optimized solution
n, k = list(map(int, input().split()))
p = list(map(int, input().split()))
c = list(map(int, input().split()))

# mv_array = [set() for _ in range(n)]
# score_mv_array = [[] for _ in range(n)]
# score_array = [0]*n

def get_sum(array):
    score_array = [0]
    for i, a in enumerate(array):
        score_array.append(score_array[i]+a)
    return max(score_array)

def get_max(array, q, mod):
    if q == 0:
        m_score = get_sum(array[:mod])
    else:
        m_score = get_sum(array+array[:mod])
        m_score = sum(array)*(q-1) + m_score
    return m_score

max_score = -float('inf')

for i in range(n):
    score = 0
    # max_score = c[i]
    score_mv_array = []
    pos = i
    start_pos = p[pos]-1
    for j in range(k):
        pos = p[pos]-1
        if j!=0 and pos == start_pos:
            # len_mv = len(score_mv_array)
            len_mv = j
            q, mod = divmod(k-j, len_mv)
            score += get_max(score_mv_array, q, mod)
            max_score = max(score, max_score)
            break
        score += c[pos]
        score_mv_array.append(c[pos])
        max_score = max(score, max_score)
    # score_array[i] = max_score

# print(max(score_array))
print(max_score)