Problem:
 Score : 400 points    Problem Statement Takahashi will play a game using a piece on an array of squares numbered 1, 2, \cdots, N . Square i has an integer C_i written on it. Also, he is given a permutation of 1, 2, \cdots, N : P_1, P_2, \cdots, P_N .  Now, he will choose one square and place the piece on that square. Then, he will make the following move some number of times between 1 and K (inclusive):   In one move, if the piece is now on Square i  (1 \leq i \leq N) , move it to Square P_i . Here, his score increases by C_{P_i} .   Help him by finding the maximum possible score at the end of the game. (The score is 0 at the beginning of the game.)      Constraints  2 \leq N \leq 5000  1 \leq K \leq 10^9  1 \leq P_i \leq N  P_i \neq i  P_1, P_2, \cdots, P_N are all different.  -10^9 \leq C_i \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  K  P_1  P_2  \cdots  P_N  C_1  C_2  \cdots  C_N       Output Print the maximum possible score at the end of the game.        Sample Input 1 5 2
2 4 5 1 3
3 4 -10 -8 8      Sample Output 1 8  When we start at some square of our choice and make at most two moves, we have the following options:   If we start at Square 1 , making one move sends the piece to Square 2 , after which the score is 4 . Making another move sends the piece to Square 4 , after which the score is 4 + (-8) = -4 .  If we start at Square 2 , making one move sends the piece to Square 4 , after which the score is -8 . Making another move sends the piece to Square 1 , after which the score is -8 + 3 = -5 .  If we start at Square 3 , making one move sends the piece to Square 5 , after which the score is 8 . Making another move sends the piece to Square 3 , after which the score is 8 + (-10) = -2 .  If we start at Square 4 , making one move sends the piece to Square 1 , after which the score is 3 . Making another move sends the piece to Square 2 , after which the score is 3 + 4 = 7 .  If we start at Square 5 , making one move sends the piece to Square 3 , after which the score is -10 . Making another move sends the piece to Square 5 , after which the score is -10 + 8 = -2 .   The maximum score achieved is 8 .       Sample Input 2 2 3
2 1
10 -7      Sample Output 2 13       Sample Input 3 3 3
3 1 2
-1000 -2000 -3000      Sample Output 3 -1000  We have to make at least one move.       Sample Input 4 10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719      Sample Output 4 29507023469  The absolute value of the answer may be enormous.

Solution (Python):
import sys

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, K = map(int, readline().split())
    P = [int(s) - 1 for s in readline().split()]
    C = list(map(int, readline().split()))

    ans = -INF
    for i in range(N):
        seen = [False] * N
        s = 0
        s_max = -INF
        scores = []
        k = 0

        while k < K and not seen[i]:
            seen[i] = True
            s += C[P[i]]
            scores.append(s)
            if s_max < s:
                s_max = s
            i = P[i]
            k += 1

        if k == K and ans < s_max:
            ans = s_max
        elif scores[-1] > 0:
            tmp = max(
                s_max,
                scores[-1] * (K // k) + max(0, max(scores[: K % k], default=0)),
                scores[-1] * (K // k - 1) + s_max,
            )
            if ans < tmp:
                ans = tmp
        else:
            if ans < s_max:
                ans = s_max

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):
N,K = [int(hoge) for hoge in input().split()]
P = [int(hoge)-1 for hoge in input().split()]
C = [int(hoge) for hoge in input().split()]
LoopSum = []
ans = 0
LoopIndex = [-1 for i in range(N)]
Loops = []
num = 0
for start in range(N):
    if -1 == LoopIndex[start]:
        LpSm = C[start]
        LoopIndex[start] = num
        route = [start]
        cur = P[start]
        while cur != start:
            LoopIndex[cur] = num
            route.append(cur)
            cur = P[cur]
            LpSm += C[cur]
        Loops.append(route)
        LoopSum.append(LpSm)
        num += 1
DekiSumAmari = [(K//len(L),sum([C[j] for j in L]),K%len(L)) for L in Loops]
for s in range(N):
    Looplen =len(Loops[LoopIndex[s]])
    score = 0
    D,S,A = DekiSumAmari[LoopIndex[s]]
    if S<=0:
        A = min(K,Looplen)
    else:
        if A==0:
            D -= 1
            A = Looplen
        score += D*S
    curpos = s
    curplus = 0
    maxplus = 0
    for i in range(min(K,Looplen)):
        if i == A:
            curplus -= S
        curplus += C[curpos]
        curpos = P[curpos]
        maxplus = max(maxplus,curplus)
    score += maxplus
    ans = max(ans,score)
if ans == 0:
    ans = max(C)
print(ans)

Solution (Python):
N,K=map(int,input().split())
P=list(map(lambda x:int(x)-1,input().split()))
C=list(map(int,input().split()))

ans=-10**18

for i in range(N):
    cnt=K
    pos=i
    tmp=[0]
    base=C[pos]
    while cnt and P[pos]!=i:
        pos=P[pos]
        tmp.append(tmp[-1]+C[pos])
        base+=C[pos]
        cnt-=1
    if P[pos]==i:
        if base>0:
            test=base*(K//len(tmp))
            cnt=K%len(tmp)
            if cnt:
                ttt=max(tmp[j] for j in range(1,cnt+1))
                if test:
                    ttt=max(ttt,0)
                test+=ttt
            ans=max(ans,test)
            if K>=len(tmp):
                test=base*(K//len(tmp)-1)
                cnt=len(tmp)-1
                ttt=max(tmp[j] for j in range(1,cnt+1))
                if test:
                    ttt=max(ttt,0)
                test+=ttt
                ans=max(ans,test)
        else:
            tmp.append(tmp[-1]+C[i])
            cnt=min(K,len(tmp)-1)
            if cnt:
                test=max(tmp[j] for j in range(1,cnt+1))
                ans=max(ans,test)
    else:
        test=max(tmp[j] for j in range(1,len(tmp)))
        ans=max(ans,test)


print(ans)

Solution (Python):

import sys,math,collections,itertools
input = sys.stdin.readline

def solve(i):
    visit = set([i])
    tmp = [] 
    
    while True:
        tmp.append(C[i-1])
        next_point = P[i-1]
        if next_point not in visit:
            visit |=set([next_point])
            i = next_point
        else:
            break
    roopLength = len(tmp)
    roop_sum = sum(tmp)
    cum_sum = list(itertools.accumulate(tmp))
    
    
    
    if roop_sum <=0:
        ans = -float('inf')
        for i in range(min(K,roopLength)):
            ans = max(ans,cum_sum[i])
    
    elif roopLength * 2 >=K:
        point = 0
        ans = -float('inf')
        for i in range(K):
            point +=  tmp[i%roopLength]
            ans = max(ans,point)
    
    elif roopLength *2 < K:
        point = roop_sum*(K//roopLength-1)
        ans = -float('inf')
        for i in range(roopLength+K%roopLength):
            point += tmp[i%roopLength]
            ans = max(ans,point)
    return ans


N,K=list(map(int,input().split()))
P=list(map(int,input().split()))
C=list(map(int,input().split()))
ans = -float('inf')
for i in range(N):
    point = solve(i+1)
    ans = max(point,ans)
print(ans)

Solution (Python):
N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [float('-inf')] + list(map(int, input().split()))
ans = max(C)
for start in range(1, N+1):
    now = start
    score = 0
    c_list = []
    for k in range(1, K+1):
        now = P[now]
        cost = C[now]
        score += cost
        c_list += [cost]
        ans = max(ans, score)
        if now == start:
            Kmk = K-k
            
            roop = (Kmk // len(c_list))
            score = score + score * max(0, roop-1)
            ans = max(score, ans)
            if roop >= 1:
                for ci in c_list:
                    score += ci
                    ans = max(score, ans)
            for i in range(Kmk % len(c_list)):
                score += c_list[i]
                ans = max(score, ans)
            break
        

print(ans)

Solution (Python):
n, k = map(int, input().split())
p = [int(i)-1 for i in input().split()]
c = [int(i) for i in input().split()]


def merge(p_a, c_a, p_b, c_b):
    p_c = []
    c_c = []
    for i, j in zip(p_a, c_a):
        p_c.append(p_b[i])
        c_c.append(j + c_b[i])
    return p_c, c_c


ans = -10**18
for i in range(n):
    co = 0
    for _ in range(min(n, k)):
        i = p[i]
        co += c[i]
        ans = max(ans, co)

if k > n:
    pp = p[:]
    cc = c[:]
    for i in range(n):
        c[i] = cc[p[i]]
    k -= n
    a = list(range(n))
    b = [0] * n
    while k > 0:
        if k % 2 == 1:
            a, b = merge(a, b, p, c)
        p, c = merge(p, c, p, c)
        k //= 2

    
    ans = max(ans,max(b))
    for i in range(n):
        co = b[i]
        i = a[i]
    
        for _ in range(n):
            i = pp[i]
            co += cc[i]
    
            ans = max(ans, co)
    

print(ans)

Solution (Python):

max2 = lambda x,y: x if x > y else y
min2 = lambda x,y: x if x < y else y

N,K = map(int,input().split())

P = tuple(map(lambda x: int(x)-1,input().split()))
C = tuple(map(int,input().split()))

Q = min2(N,K)

acc = [0]*N
visited = [-1]*N
last = [0]*N


res = -10**9

for p in range(N):
    c = 0
    v = P[p]
    for j in range(Q):
        if visited[v] == j:
            break
        visited[v] = j
        acc[v] = c
        c += C[v]
        last[v] = j
        v = P[v]
        res = max2(c,res)

    i = last[v]
    j += 1

    delta = c - acc[v]
    
    if delta > 0:
        remaining = K - i
        cycle = j-i
        if remaining < cycle:
            c = acc[v]
            for _ in range(remaining):
                c += C[v]
                res = max2(res, c)
                v = P[v]
        else:
            c = acc[v]+(remaining//cycle - 1)*delta
            remaining = cycle + remaining%cycle
            for _ in range(remaining):
                c += C[v]
                res = max2(res, c)
                v = P[v]

print(res)

Solution (Python):
n,k=map(int,input().split())

p=[i-1 for i in list(map(int,input().split()))]
c=list(map(int,input().split()))

ansF=-1000000000000000000
for i in range(n):
    
    check=[False]*n
    
    turns=[]
    
    now=i
    while check[now]==False:
        check[now]=True
        turns.append(now)
        now=p[now]
    
    ans=0
    
    
    spare=turns.index(now)
    if spare>=k:
        for j in range(k):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        continue
    for j in range(spare):
        ans+=c[turns[j]]
        ansF=max(ans,ansF)
    turns=turns[spare:]
    spare=k-spare
    
    l=len(turns)
    
    
    x=0
    for j in range(l):
        x+=c[turns[j]]
    
    if spare<=l:
        for j in range(spare):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        continue
    
    
    if x>=0:
        ans+=(x*(spare//l-1))
        ansF=max(ans,ansF)
        for j in range(l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
        for j in range(spare%l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
    
    else:
        for j in range(l):
            ans+=c[turns[j]]
            ansF=max(ans,ansF)
print(ansF)

Solution (Python):
def solve(shoki):
    global n,k,p,c
    sude=[-1]*n
    sude[shoki]=0
    ten=[0]
    now=shoki
    ishuu_kai=0
    ishuu_ten=0
    for i in range(n):
        now=p[now]
        if(sude[now]<0):
            sude[now]=i+1
            ten.append(ten[-1]+c[now])
        else:
            ten.append(ten[-1]+c[now])
            ishuu_kai=i+1-sude[now]
            ishuu_ten=ten[-1]-ten[sude[now]]
            break
    
    
    if(ishuu_ten>0):
        now=shoki
        for i in range(ishuu_kai):
            ten[i]+=((k-i)//ishuu_kai)*ishuu_ten
            now=p[now]

    
    if(k>ishuu_kai):
        return max(ten)
    else:
        return max(ten[1:k+1])


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

for i in range(n):
    p[i]-=1


ans=[]
for i in range(n):
    ans.append(solve(i))

print(max(ans))

Solution (Python):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))

ans = -float('inf')
for i in range(N):
    cnt = 0
    k = 0
    done = set()
    S = []
    while i not in done:
        done.add(i)
        ni = P[i] - 1
        if len(S):
            S.append(S[-1] + C[ni])
        else:
            S.append(C[ni])
        i = ni
    if K <= len(S):
        score = max(S[:K])
    elif S[-1] <= 0:
        score = max(S)
    else:
        score1 = S[-1] * ((K // len(S)) - 1)
        score1 += max(S)
        score2 = S[-1] * (K // len(S))
        r = K % len(S)
        if r != 0:
            score2 += max(0, max(S[:r]))
        score = max(score1, score2)
    ans = max(ans, score)
print(ans)

Solution (Python):
N, K = map(int, input().split())
P = list(map(lambda x:int(x)-1, input().split()))
C = list(map(int, input().split()))

ans = -float('inf')

for start in range(N):
    loop_len = 1
    pos = P[start]
    score = C[pos]
    scores = [score]
    while pos != start:
        loop_len += 1
        pos = P[pos]
        score += C[pos]
        scores.append(score)
    loops = (K-1)//loop_len
    if score > 0:
        cand = max(0, score * loops) + max(scores[:(K-loop_len * loops)])
    else:
        cand = max(scores[:min(K, loop_len)])
    ans = max(ans, cand)
print(ans)

Solution (Python):

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

ans = []
for u in range(N):
    v = P[u] - 1
    cnt = C[v]
    val = cnt
    jump = 1

    
    while v != u and jump < K:
        v = P[v] - 1
        cnt += C[v]
        val = max(val, cnt)
        jump += 1

    
    if jump < K:
        res = max(0, K // jump - 2)
        cnt += cnt * res
        val = max(val, cnt)
        jump += jump * res

    
    while jump < K:
        v = P[v] - 1
        cnt += C[v]
        val = max(val, cnt)
        jump += 1

    ans.append(val)

print(max(ans))

Solution (Python):


N, K = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))

def do(start, k):
    score = 0
    max_score = -10 ** 10
    visited = set()
    now = start
    count = 0
    while True:
        next_node = P[now]
        if next_node in visited:
            if score <= 0:
                return max_score
            else:
                n = k // count
                score = score * (n-1)
                max_score = score
                k %= count; k += count
                for _ in range(k):
                    next_node = P[now]
                    score += C[next_node]
                    max_score = max(max_score, score)
                    now = next_node
                return max_score
        
        score += C[next_node]
        count += 1
        max_score = max(max_score, score)
        now = next_node
        visited.add(now)
        if count == k:
            return max_score

ans = -10 ** 10
for start in range(1, N+1):
    ans = max(ans, do(start, K))

print(ans)

Solution (Python):
R = lambda: map(int, raw_input().split())
n, k = R()
p, c = R(), R()
p = [x - 1 for x in p]
vis = [False] * n
ans = max(c)

for i in xrange(n):
    if vis[i]:
        continue
    t = [c[i]]
    j = p[i]
    while j != i:
        vis[j] = True
        t.append(c[j])
        j = p[j]

    m = len(t)
    ts = sum(t)
    for i in xrange(len(t)):
        tmp = min(k, m)
        s = 0
        for j in xrange(tmp):
            s += t[(i + j) % m]
            tk = k - j - 1
            ans = max(ans, s + tk / m * max(0, ts))
print ans

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7


def resolve():
    n, k = map(int, input().split())
    P = list(map(int, input().split()))
    C = list(map(int, input().split()))

    res = -f_inf
    for now in range(n):
        cnt = 0
        score = [0]
        visited = set()
        for j in range(k):
            next_now = P[now] - 1
            if next_now not in visited:
                score.append(score[-1] + C[next_now])
                visited.add(next_now)
                now = next_now
                cnt += 1
            else:
                break
        score.pop(0)
        if k - cnt == 0:
            res = max(res, max(score))
        else:
            if score[-1] <= 0:
                res = max(res, max(score))
            else:
                q, r = divmod(k, cnt)
                if r == 0:
                    res = max(res, max(score) + score[-1] * (q - 1))
                else:
                    res = max(res, max(score[:r]) + score[-1] * q, max(score[r:]) + score[-1] * (q - 1))
    print(res)


if __name__ == '__main__':
    resolve()

Solution (Python):
import sys
import heapq, functools, collections
import math, random
from collections import Counter, defaultdict






def solve(arr,brr,k):  
    console("----- solving ------")
    arr = [a-1 for a in arr]

    console(arr)
    console(brr)
    console(k)

    if all(b <= 0 for b in brr):
        return max(brr)

    visited = [False for _ in arr]
    cycles = []

    for start,_ in enumerate(arr):
        if visited[start]:
            continue
        cur_cycle = [start]
        current = start
        visited[current] = True

        while arr[current] != start:
            current = arr[current]
            cur_cycle.append(current)
            visited[current] = True
        
        cycles.append(cur_cycle)

    res = -float("inf")

    for cycle in cycles:
        console(cycle)

        cs = 0
        psum = []
        for idx in cycle+cycle:
            cs += brr[idx]
            psum.append(cs)
        
        lengths = [-float("inf") for i in cycle]
        for start,_ in enumerate(cycle):
            for length,_ in enumerate(cycle):
                lengths[length] = max(lengths[length], psum[start+length] - psum[start])
    
        console([brr[idx] for idx in cycle])
        full_cycle = sum([brr[idx] for idx in cycle])

        if k < len(cycle) or full_cycle <= 0:
            curres = max(lengths[:k+1])
            console(curres)
            res = max(res, curres)
            continue
        
        console(lengths, full_cycle)

        num_cycles = (k // len(cycle)) - 1
        res_baseline = num_cycles * full_cycle
        remainder = k % len(cycle)

        curres1 = res_baseline + max(lengths)
        curres2 = res_baseline + full_cycle + max(lengths[:remainder+1])

        console(curres1)
        console(curres2)

        curres = max(curres1, curres2)
        console(curres)
        res = max(res, curres)

    console(cycles)

    
    return int(res)  


def console(*args):  
    
    return




for case_num in [1]:
    
    

    
    
    
    
    

    
    _,k = list(map(int,input().split()))
    arr = list(map(int,input().split()))
    brr = list(map(int,input().split()))

    
    
    
    
    
    

    res = solve(arr,brr,k)  
    
    
    

    
    print(res)

Solution (Python):
import sys,collections as cl,bisect as bs
sys.setrecursionlimit(100000)
input = sys.stdin.readline
mod = 10**9+7
Max = sys.maxsize
def l(): 
    return list(map(int,input().split()))
def m(): 
    return map(int,input().split())
def onem(): 
    return int(input())
def s(x): 
    a = []
    if len(x) == 0:
        return []
    aa = x[0]
    su = 1
    for i in range(len(x)-1):
        if aa != x[i+1]:
            a.append([aa,su])
            aa = x[i+1]
            su = 1
        else:
            su += 1
    a.append([aa,su])
    return a
def jo(x): 
    return " ".join(map(str,x))
def max2(x): 
    return max(map(max,x))
def In(x,a): 
    k = bs.bisect_left(a,x)
    if k != len(a) and a[k] ==  x:
        return True
    else:
        return False

def pow_k(x, n):
    ans = 1
    while n:
        if n % 2:
            ans *= x
        x *= x
        n >>= 1
    return ans

"""
def nibu(x,n,r):
    ll = 0
    rr = r
    while True:
        mid = (ll+rr)//2

    if rr == mid:
        return ll
    if (ここに評価入れる):
        rr = mid
    else:
        ll = mid+1
"""


n,k = m()

masc = [[0 for i in range(n+1)] for j in range(n)]
maxsu = [[0 for i in range(n+1)] for j in range(n)]

roop = [0 for i in range(n)]

p = l()

c = l()

for i in range(n):
    count = 0
    su = 0
    now = i
    for j in range(n+1):
        now = p[now] - 1
        count += 1
        su += c[now]
        masc[i][count-1] = su
        if count == 1:
            maxsu[i][count-1] = su
        else:
            maxsu[i][count-1] = max(maxsu[i][count-2],su)
        if i == now:
            roop[i] = count
            break

ans = -Max

for i in range(n):
    if k <= roop[i]:
        ans = max(ans,maxsu[i][k-1])
    else:
        if masc[i][roop[i]-1] < 0:
            ans = max(ans,maxsu[i][roop[i]-1])
        else:
            ans = max(ans,(k//roop[i]) * masc[i][roop[i]-1] + maxsu[i][k % roop[i]-1],(k//roop[i] - 1) * masc[i][roop[i]-1] + maxsu[i][roop[i]-1])
print(ans)

Solution (Python):
def main():
    (n,k),p,c=[[*map(int,t.split())]for t in open(0)]
    m=-10**18
    for i in range(n):
        s=i
        t=1
        x=c[s]
        while p[s]-1!=i:
            s=p[s]-1
            t+=1
            x+=c[s]
        if x>0:
            a=(k//t-1)*x
            if a>m:m=a
            s=i
            for _ in range(k%t+t):
                s=p[s]-1
                a+=c[s]
                if a>m:m=a
        else:
            a=0
            s=i
            for _ in range(min(k,t)):
                s=p[s]-1
                a+=c[s]
                if a>m:m=a
    print(m)
main()

Solution (Python):
def solve(n,x,k):
  ans=-10**20
  s=0
  sx=sum(x)
  for i in range(n):
    if (i+1)>k:break
    s+=x[i]
    d=((k-i-1)//n)*sx
    ans=max(ans,s+d,s)
  return ans

n,k=map(int,input().split())
p=list(map(lambda x:int(x)-1,input().split()))
c=list(map(int,input().split()))
ans=-10**20
for i in range(n):
  x=[c[i]]
  j=p[i]
  while i!=j:
    x.append(c[j])
    j=p[j]
  x=x[1:]+[x[0]]
  ans=max(ans,solve(len(x),x,k))
print(ans)

Solution (Python):

import os
import sys
from io import BytesIO, IOBase

BUFSIZE = 8192


class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = "x" in file.mode or "r" not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b"\n") + (not b)
            ptr = self.buffer.tell()
            self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr)
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            self.buffer.truncate(0), self.buffer.seek(0)


class IOWrapper(IOBase):
    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode("ascii"))
        self.read = lambda: self.buffer.read().decode("ascii")
        self.readline = lambda: self.buffer.readline().decode("ascii")


sys.stdin, sys.stdout = IOWrapper(sys.stdin), IOWrapper(sys.stdout)
input = lambda: sys.stdin.readline().rstrip("\r\n")


from math import gcd, ceil



def prod(a):
    ans = 1
    for each in a:
        ans = (ans * each)
    return ans

def lcm(a, b): return a * b // gcd(a, b)


def binary(x, length=16):
    y = bin(x)[2:]
    return y if len(y) >= length else "0" * (length - len(y)) + y
from math import inf

for _ in range(int(input()) if not True else 1):
    
    n, k = map(int, input().split())
    
    
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    ans = -inf
    for i in range(n):
        st = set()
        st.add(i)
        cur = i
        x = []
        while p[cur]-1 not in st:
            cur = p[cur]-1
            st.add(cur)
            x += [c[cur]]
        x += [c[p[cur]-1]]

        pre = [0]*len(x)
        pre[0] = x[0]
        for i in range(1, len(x)):
            pre[i] = pre[i-1] + x[i]
        if len(x) >= k:
            ans = max(ans, max(pre[:k]))
        else:
            kc = k
            kcc = k
            anss = 0
            if pre[-1] > 0:
                anss += pre[-1]*(kc // len(x))
                kc = kc % len(x)
                if kc:
                    anss += max(pre[:kc])
                ans = max(ans, anss, max(pre)+(pre[-1]*((kcc // len(x))-1)))
            else:
                ans = max(ans, max(pre))
    print(ans)

Solution (Python):

from collections import defaultdict, deque, Counter, OrderedDict
from bisect import bisect_left, bisect_right
from functools import reduce, lru_cache
from heapq import heappush, heappop, heapify

import itertools, bisect
import math, fractions
import sys, copy

def L(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline().rstrip())
def SL(): return list(sys.stdin.readline().rstrip())
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI1(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return [list(x) for x in sys.stdin.readline().split()]
def IR(n): return [I() for _ in range(n)]
def LIR(n): return [LI() for _ in range(n)]
def LIR1(n): return [LI1() for _ in range(n)]
def SR(n): return [SL() for _ in range(n)]
def LSR(n): return [LS() for _ in range(n)]
def LR(n): return [L() for _ in range(n)]

def perm(n, r): return math.factorial(n) // math.factorial(r)
def comb(n, r): return math.factorial(n) // (math.factorial(r) * math.factorial(n-r))

alphabets = "abcdefghijklmnopqrstuvwxyz"
ALPHABETS = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"

sys.setrecursionlimit(1000000)
dire = [[1, 0], [0, 1], [-1, 0], [0, -1]]
dire8 = [[1, 0], [1, 1], [0, 1], [-1, 1], [-1, 0], [-1, -1], [0, -1], [1, -1]]
MOD = 1000000007
INF = float("inf")

def main():
    N, K = LI()
    P = LI1()
    C = LI()

    visit = [False] * N
    where = [-1] * N

    group = []
    group_sum = []
    for i in range(N):
        if visit[i]: continue
        
        now = i
        tmp = []
        cum = 0
        while not visit[now]:
            tmp.append(now)
            visit[now] = True
            where[now] = len(group)
            cum += C[now]
            now = P[now]
        group.append(tmp)
        group_sum.append(cum)

    ans = -INF

    for i in range(N):
        g = group[where[i]]

        if len(g) <= K:
            loop_count = K // len(g) - 1
            rest = K - loop_count * len(g)
        else:
            loop_count = 0
            rest = K

        loop_score = group_sum[where[i]]

        tmp = C[P[i]]
        tmp_max = C[P[i]]
        now = P[i]
        for _ in range(rest-1):
            now = P[now]
            tmp += C[now]
            tmp_max = max(tmp, tmp_max)
        ans = max(ans, max(tmp_max, tmp_max + loop_count * loop_score))
    print(ans)






if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = sys.stdin.readline
n, k = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
for i in range(n):
    P[i] -= 1


    
    
    
    
    
    
    
    
    
    


V = [0] * n
ans = -float("inf")
an = 0
for i in range(n):
    if V[i] == 0:
        A = []
        V[i] = 1
        ii = P[i]
        V[ii] = 1
        A.append(C[ii])
        while ii != i:
            ii = P[ii]
            V[ii] = 1
            A.append(C[ii])
        
        an = 0
        anb=0
        anb2=0
        kb=k
        kb2=k
        if sum(A) > 0:
            anb += sum(A) * (k//len(A))
            kb = k%len(A)
        if k >= len(A) and sum(A) > 0:
            anb2 += sum(A) * (k//len(A)-1)
            kb2 = k % len(A) + len(A)
        A += A
        S = [A[0]]
        
        for i in range(1,len(A)):
            S.append(S[-1]+A[i])
        
        anc = 0
        for i in range(len(S)):
            for j in range(i+1, min(i+kb2+1,len(S))):
                anc = max(anc,S[j]-S[i])

        for i in range(len(S)):
            for j in range(i+1, min(i+kb+1,len(S))):
                an = max(an,S[j]-S[i])

        ans = max(an+anb,anc+anb2,ans)
            
if ans == 0 and max(C) < 0:
    ans = max(C)
print(ans)

Solution (Python):
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
INF = 10 ** 18


def solve(v):
    res = []
    set_ = set()
    tot = 0
    while True:
        nxt_v = p[v] - 1
        cost = c[nxt_v]
        if nxt_v not in set_:
            set_.add(nxt_v)
            tot += cost
            res.append(tot)
            v = nxt_v
        else:
            break
    return res, tot


ans = -INF


for v in range(n):
    ans = max(c[v], ans)

for v in range(n):
    res, tot = solve(v)
    if tot < 0:
        for i in range(min(k, len(res))):
            ans = max(res[i], ans)
    else:
        lap, rem = divmod(k, len(res))
        tmp = lap * tot
        if lap > 0:
            ans = max(ans, tmp)
        for i in range(min(rem, len(res))):
            ans = max(tmp + res[i], ans)
            
        if lap == 0:
            continue
        lap -= 1
        tmp = lap * tot
        for i in range(min(k, len(res))):
            ans = max(tmp + res[i], ans)
            
print(ans)