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):
N, KK = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))

cnt = [1] * (N+1)
retsu = []
for i in range(1,N+1):
    idx = i
    r = []
    for _ in range(N):
        if cnt[idx] == 0:
            break
        r.append(C[P[idx]])
        cnt[idx] = 0
        idx = P[idx]
    if r:
        retsu.append(r)

ans = -1 * (10 ** 10)
for z in retsu:
    K = KK
    s = sum(z)
    l = len(z)
    if K <= l:
        plus = 0
    elif s <= 0:
        plus = 0
        K = l
    else:
        plus = s * (K // l)
        if K % l == 0:
            plus -= s
    K %= l
    if K == 0:
        K = l
    
    moto = z + z
    point = [[0] * l for _ in range(l+K-1)]
    kari = -1 * (10 ** 10)
    for i in range(l+K-1):
        for j in range(l):
            if i == j:
                point[i][j] = moto[i]
            elif i - j >= K or i < j:
                continue
            else:
                point[i][j] = moto[i] + point[i-1][j]
            kari = max(kari, point[i][j])
    ans = max(ans, plus + kari)
print(ans)

Solution (Python):
n,k=map(int,input().split())
P=list(map(int,input().split()))
for i in range(n):
	P[i]-=1
C=list(map(int,input().split()))
ANS=-float('inf')
for i in range(n):
    snp=P[i]
    r=C[snp]
    L=[r]
    c=0
    np=P[snp]
    while True:
        if c==k-1:
            ANS=max(max(L),ANS)
            break
        if np==snp:
            y=k%(c+1)
            m=k//(c+1)
            if y==0:
                ANS=max(max(L),max(L)+(m-1)*L[-1],ANS)
                break
            else:
                
                
                ANS=max(max(L),max(max(L[:y]),0)+m*L[-1],ANS)
                break
        r+=C[np]
        L.append(r)
        np=P[np]
        c+=1
print(ANS)

Solution (Python):
N,K = map(int, input().split())
PList = list(map(int, input().split()))
CList = list(map(int, input().split()))

ans = -1*(10**18)
for si in range(N):
  x = si
  s = list()
  total = 0
  l = 0
  while(1):
    x = PList[x]-1
    s.append(CList[x])
    l += 1
    total += CList[x]
    if x == si:
      break
  t = 0
  for i in range(l):
    t += s[i]
    if i+1 > K:
      break
    now = t
    if total > 0:
      e = (K-i-1)//l
      now += total*e
    ans = max(ans, now)  
print(ans)

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

def mymax(max_variable, candidate):
    if max_variable is None:
        return candidate
    else:
        return max(max_variable, candidate)

max_cost = None
for start in range(n):
    seen = []
    next_ = p[start]
    cost_sum = []
    cost = 0
    while next_ != start:
        seen.append(next_)
        cost += c[next_]
        cost_sum.append(cost)
        next_ = p[next_]

    seen.append(start)
    cost += c[start]
    cost_sum.append(cost)

    l = len(seen)
    s = cost_sum[-1]
    for end in range(len(seen)):
        moves = end + 1
        remain_moves = k - moves
        if remain_moves < 0:
            continue
        cand_cost = cost_sum[end] + max(0, s) * int(remain_moves / l)
        max_cost = mymax(max_cost, cand_cost)
print(max_cost)

Solution (Python):
import sys
input = sys.stdin.buffer.readline

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

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

c = list(map(int,input().split()))
used = [False]*n

edge = []

for i in range(n):
    if used[i]:
        continue
    now = i
    edge.append([])

    while True:
        if used[now]:
            break
        used[now] = True
        edge[-1].append(c[now])
        now = p[now]

res = -10**9
for i in range(len(edge)):
    s = sum(edge[i])
    m = len(edge[i])

    for j in range(m):
        tmp = 0
        ctr = 0
        for h in range(j+1,m):
            ctr += 1
            tmp += edge[i][h]
            if ctr <= k:
                res = max(res,tmp,tmp+((k-ctr)//m)*s)
        for h in range(j+1):
            ctr += 1
            tmp += edge[i][h]
            if ctr <= k:
                res = max(res,tmp,tmp+((k-ctr)//m)*s)
print(res)

Solution (Python):
import sys
import resource
sys.setrecursionlimit(10000)
n,k=map(int,input().rstrip().split())
p=list(map(int,input().rstrip().split()))
c=list(map(int,input().rstrip().split()))
def find(start,now,up,max,sum,count,flag):
    if start==now:
        flag+=1
    if start==now and flag==2:
        return [max,sum,count]
    elif count==up:
        return [max,sum,count]
    else:
        count+=1
        sum+=c[p[now-1]-1]
        if max<sum:
            max=sum
        return find(start,p[now-1],up,max,sum,count,flag)
result=-10000000000
for i in range(1,n+1):
    m=find(i,i,n,c[p[i-1]-1],0,0,0)
    if m[2]>=k:
        m=find(i,i,k,c[p[i-1]-1],0,0,0)
        if m[0]>result:
            result=m[0]
        ans=result
    elif m[1]<=0:
        if m[0]>result:
            result=m[0]
        ans=result
    else:
        w=k%m[2]
        if w==0:
            w=m[2]
        spe=find(i,i,w,c[p[i-1]-1],0,0,0)[0]
        if m[1]+spe>m[0] and m[1]*(k-w)//m[2]+spe>result:
            result=m[1]*(k-w)//m[2]+spe
        elif m[1]+spe<=m[0] and m[1]*((k-w)//m[2]-1)+m[0]>result:
            result=m[1]*((k-w)//m[2]-1)+m[0]
        ans=result
print(ans)

Solution (Python):
n,k=map(int,input().split())
p=[int(i)-1for i in input().split()]
c=list(map(int,input().split()))
ans=-10**9
for i in range(n):
    start=i
    cycle=[0]
    for _ in range(n):
        i=p[i]
        cycle+=[cycle[-1]+c[i]]
        if i==start:break
    S,L=cycle[-1],len(cycle)-1
    if S<=0:ans=max(ans,max(cycle[1:k+1]))
    else:ans=max(ans,max(0,k//L-1)*S+max(max(cycle[:k+1]),max(cycle[:k%L+1])+S*(k>L))) 
print(ans)

Solution (Python):
n,k=map(int,input().split())
p=[int(i)-1for i in input().split()]
c=list(map(int,input().split()))
ans=-10**9
for i in range(n):
    start=i
    cycle=[0]
    for _ in range(n):
        i=p[i]
        cycle+=[cycle[-1]+c[i]]
        if i==start:break
    S,L=cycle[-1],len(cycle)-1
    if S<=0:ans=max(ans,max(cycle[1:k+1]))
    else:
        if k>L:ans=max(ans,(k//L-1)*S+max(max(cycle),max(cycle[:k%L+1])+S)) 
        else:ans=max(ans,max(cycle[:k+1]))
print(ans)

Solution (Python):
import sys
import resource
sys.setrecursionlimit(10000)
n,k=map(int,input().rstrip().split())
p=list(map(int,input().rstrip().split()))
c=list(map(int,input().rstrip().split()))
def find(start,now,up,max,sum,count,flag):
    if start==now:
        flag+=1
    if start==now and flag==2:
        return [max,sum,count]
    elif count==up:
        return [max,sum,count]
    else:
        count+=1
        sum+=c[p[now-1]-1]
        if max<sum:
            max=sum
        return find(start,p[now-1],up,max,sum,count,flag)
kara=[-10000000000]
for i in range(1,n+1):
    m=find(i,i,n,c[p[i-1]-1],0,0,0)
    if m[2]>=k:
        m=find(i,i,k,c[p[i-1]-1],0,0,0)
        if m[0]>kara[0]:
            kara[0]=m[0]
        result=kara[0]
    elif m[1]<=0:
        if m[0]>kara[0]:
            kara[0]=m[0]
        result=kara[0]
    else:
        w=k%m[2]
        if w==0:
            w=m[2]
        spe=find(i,i,w,c[p[i-1]-1],0,0,0)[0]
        if m[1]+spe>m[0] and m[1]*(k-w)//m[2]+spe>kara[0]:
            kara[0]=m[1]*(k-w)//m[2]+spe
        elif m[1]+spe<=m[0] and m[1]*((k-w)//m[2]-1)+m[0]>kara[0]:
            kara[0]=m[1]*((k-w)//m[2]-1)+m[0]
        result=kara[0]
print(result)

Solution (Python):
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=-10**18

for si in range(n):
    score=[]
    x=si
    while(1):
        x=p[x]
        score.append(c[x])
        if(x==si):
            break
    l=len(score)
    accum=[score[0]]
    for i in range(1,l):
        accum.append(score[i]+accum[i-1])
    total=sum(score)
    z=k//l
    if(total>0):
        for i in range(l):
            if(((z-1)*l+i)>=0):
                tmp=accum[i]+total*(z-1)
                ans=max(ans,tmp)
            if((z*l+i)<k):
                tmp=accum[i]+total*z
                ans=max(ans,tmp)
    else:
        for i in range(l):
            if(i<k):
                tmp=accum[i]
                ans=max(ans,tmp)
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()))
    
visited = [False] * n
ans = max(c)

for i in range(n):
    if visited[i]:
        continue
    arr = []
    u = i
    while not visited[u]:
        arr.append(c[u])
        visited[u] = True
        u = p[u]
    s = sum(arr) * (k // len(arr))
    rem = k % len(arr)
    if k // len(arr) >= 1:
        s -= sum(arr)
        rem += len(arr)
        
    arr += arr + arr
    pref_sum = [0]
    for i in arr:
        pref_sum.append(pref_sum[-1] + i)
    
            
    for f in range(len(arr) // 2):
        
        for g in range(f + 1, len(pref_sum)):
            if g - f <= k:
                ans = max(ans, pref_sum[g] - pref_sum[f])
            if g - f <= rem:
                ans = max(ans, s + pref_sum[g] - pref_sum[f])
print(ans)

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

p = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

loop_max = []
loop_len = []
S = []
ans = []

for i in range(len(p)):
    now = i
    temp_len = 0
    temp_s = 0
    temp_l = []
    while True:
        now = p[now] - 1
        temp_len += 1
        temp_s += c[now]
        temp_l.append(temp_s)

        
        if now == i:
            break

    loop_len.append(temp_len)
    loop_max.append(temp_l)
    S.append(temp_s)

for i in range(len(S)):
    mod = k % loop_len[i] if k % loop_len[i] != 0 else loop_len[i]
    if S[i] > 0:
        if max(loop_max[i][:mod]) > 0:
            ans.append(((k-1)//loop_len[i])*S[i] + max(loop_max[i][:mod]))
        else:
            ans.append(((k - 1) // loop_len[i]) * S[i])
    else:
        ans.append(max(loop_max[i]))

print(max(ans))

Solution (Python):
from itertools import accumulate 

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

ans = -10**18-1
seen = [False]*N
for i in range(N):
    if seen[i]:
        continue
    loop = []
    now = i
    while seen[now] == False:
        seen[now] = True
        loop.append(C[now])
        now = P[now]
    loop_size = len(loop)
    loop_score = sum(loop)
    cumsum = list(accumulate(loop+loop))
    for j in range(1, min(K, loop_size)+1):
        for l in range(loop_size):
            r = l+j
            subseq = cumsum[r] - cumsum[l]
            ans = max(ans, subseq, subseq+loop_score*((K-j)//loop_size))
print(ans)

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

p = [int(x) for x in input().split()]
c = [int(x) for x in input().split()]

p_flag = [0 for _ in range(len(p))]
loop_max = []
loop_len = []
S = []
S_max = []
ans = []

for i in range(len(p)):
    
    
    now = i
    temp_len = 0
    temp_s = 0
    S_max = - (10**9 + 1)
    temp_l = []
    while True:
        now = p[now] - 1
        temp_len += 1
        temp_s += c[now]
        temp_l.append(temp_s)
        p_flag[now] = 1

        
        if now == i:
            break

    loop_len.append(temp_len)
    loop_max.append(temp_l)
    S.append(temp_s)

for i in range(len(S)):
    mod = k % loop_len[i] if k % loop_len[i] != 0 else loop_len[i]
    if S[i] > 0:
        if max(loop_max[i][:mod]) > 0:
            ans.append(((k-1)//loop_len[i])*S[i] + max(loop_max[i][:mod]))
        else:
            ans.append(((k - 1) // loop_len[i]) * S[i])
    else:
        ans.append(max(loop_max[i]))



print(max(ans))

Solution (Python):
from itertools import accumulate 

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

ans = -10**18-1
seen = [False]*N
for i in range(N):
    if seen[i]:
        continue
    loop = []
    now = i
    while seen[now] == False:
        seen[now] = True
        loop.append(C[now])
        now = P[now]
    loop_size = len(loop)
    loop_score = sum(loop)
    cumsum = [0]+list(accumulate(loop+loop))
    for j in range(1, min(K, loop_size)+1):
        for l in range(loop_size+1):
            r = l+j
            subseq = cumsum[r] - cumsum[l]
            ans = max(ans, subseq, subseq+loop_score*((K-j)//loop_size))
print(ans)

Solution (Python):
def d_moving_piece():
    N, K = [int(i) for i in input().split()]
    P = [int(i) - 1 for i in input().split()]  
    C = [int(i) for i in input().split()]

    
    is_visited = [False] * N
    cycles = []  
    for i in range(N):
        if is_visited[i]:
            continue

        current = i
        t = []
        while not is_visited[current]:
            is_visited[current] = True
            t.append(C[current])
            current = P[current]
        cycles.append(t)

    ans = -float('inf')
    for s in cycles:
        m = len(s)

        
        total = [0] * (2 * m + 1)
        for i in range(2 * m):
            total[i + 1] = total[i] + s[i % m]

        reminder = [-float('inf')] * m  
        for i in range(m):
            for j in range(m):
                reminder[j] = max(reminder[j], total[i + j] - total[i])

        
        for r in range(m):
            if r > K:
                continue  

            q = (K - r) // m  
            if r == 0 and q == 0:
                continue  

            if total[m] > 0:
                
                ans = max(ans, reminder[r] + total[m] * q)
            elif r > 0:
                
                ans = max(ans, reminder[r])
    return ans

print(d_moving_piece())

Solution (Python):
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=max(c)
for i in range(n):
    f=i
    r=0
    l=[]
    while True:
        f=p[f]
        l.append(c[f])
        r+=c[f]
        if f==i:
            break
    t=0
    for j in range(len(l)):
        t+=l[j]
        if j+1>k:
            break
        ret=t
        if r>0:
            e=(k-j-1)//len(l)
            ret+=r*e
        ans=max(ans,ret)
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()))

move_db = [[0] * N for _ in range(65)]
point_db = [[0] * N for _ in range(65)]
maxpoint_db = [[0] * N for _ in range(65)]

for i, (p, c) in enumerate(zip(P, C)):
    move_db[0][i] = p
    point_db[0][i] = c
    maxpoint_db[0][i] = c

for i in range(40):
    for j in range(N):
        move_db[i+1][j] = move_db[i][move_db[i][j]]
        point_db[i+1][j] = point_db[i][move_db[i][j]] + point_db[i][j]
        maxpoint_db[i+1][j] = max(maxpoint_db[i][j], point_db[i][j] + maxpoint_db[i][move_db[i][j]])

res = -10 ** 19
for i in range(N):
    tmp, now = 0, i
    for d in range(32):
        if K&(1<<d):
            res = max(res, tmp + maxpoint_db[d][now])
            tmp += point_db[d][now]
            now = move_db[d][now]

print(res)

Solution (Python):
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=max(c)
for i in range(n):
    f=i
    r=0
    l=[]
    while True:
        f=p[f]
        l.append(c[f])
        r+=c[f]
        if f==i:
            break
    t=0
    for j in range(len(l)):
        t+=l[j]
        ret=t
        if r>0:
            e=(k-j-1)//len(l)
            ret+=r*e
        ans=max(ans,ret)
print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
from heapq import heappop, heappush
from math import sqrt
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul, itemgetter
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7





class Roop:
    def __init__(self, array):
        self.n = len(array)
        self.array = array
        
        self.roops = []
        
        self.roop_dict = [-1] * self.n
        
        self.opt_dic = [-1] * self.n
        ignore = [-1] * self.n
        cnt = 0
        for i in range(self.n):
            if ignore[i] >= 0:
                continue
            opt = [i]
            
            self.opt_dic[i] = 0
            c = 1
            
            ignore[i] = cnt
            
            to = array[i]
            
            while True:
                if ignore[to] == cnt:
                    
                    for j in range(self.opt_dic[to], len(opt)):
                        self.roop_dict[opt[j]] = cnt
                    self.roops.append(opt[self.opt_dic[to]:])
                    
                    cnt += 1
                    break
                opt.append(to)
                ignore[to] = cnt
                self.opt_dic[to] = c
                c += 1
                to = array[to]

    
    def roop_n(self, x):
        return self.roop_dict[x]

    
    
    def inspect(self, x):
        if self.roop_n(x) == -1:
            return False
        return self.roops[self.roop_dict(x)]

    
    def roop_len(self, x):
        return len(self.roops[self.roop_n(x)])

    
    def move(self, x, k):
        cnt = k
        to = x
        
        
        head = []
        
        tail = []
        
        time = -1
        res = 0
        while cnt > 0:
            to = self.array[to]
            cnt -= 1
            
            if time == -1 and self.roop_n(to) >= 0:
                r = self.roops[self.roop_n(to)]
                time = (cnt // len(r))
                cnt -= time * len(r)
            
            if time == -1:
                head.append(to)
            
            else:
                tail.append(to)
        
        
        
        
        
        
        
        return to

"""
N, A = getNM()
A -= 1
K = getN()
B = [i - 1 for i in getList()]
roop = Roop(B)
print(roop.move(A, K) + 1)

"""

"""

N, K = getNM()
N -= 1
A = [i - 1 for i in getList()]
roop = Roop(A)
print(roop.move(0, K) + 1)
"""



N, K = getNM()
P = [i - 1 for i in getList()]
C = getList()

roop = Roop(P)


ans = -float('inf')
for r in roop.roops:
    n = len(r)
    
    alta = []
    for i in range(n):
        alta.append(C[r[i]])
    
    one_roop = sum(alta)
    alta += alta
    imos = [0]
    for i in range(len(alta)):
        imos.append(imos[i] + alta[i])

    t = min(n, K)
    for i in range(n):
        
        for j in range(1, t + 1):
            if one_roop >= 0:
                opt = (imos[i + j] - imos[i]) + ((K - j) // n) * one_roop
            else:
                opt = imos[i + j] - imos[i]
            ans = max(ans, opt)

print(ans)

Solution (Python):
def getN():
    return int(input())
def getNM():
    return map(int, input().split())
def getList():
    return list(map(int, input().split()))
def getArray(intn):
    return [int(input()) for i in range(intn)]
def input():
    return sys.stdin.readline().rstrip()
def rand_N(ran1, ran2):
    return random.randint(ran1, ran2)
def rand_List(ran1, ran2, rantime):
    return [random.randint(ran1, ran2) for i in range(rantime)]
def rand_ints_nodup(ran1, ran2, rantime):
  ns = []
  while len(ns) < rantime:
    n = random.randint(ran1, ran2)
    if not n in ns:
      ns.append(n)
  return sorted(ns)

def rand_query(ran1, ran2, rantime):
  r_query = []
  while len(r_query) < rantime:
    n_q = rand_ints_nodup(ran1, ran2, 2)
    if not n_q in r_query:
      r_query.append(n_q)
  return sorted(r_query)

from collections import defaultdict, deque, Counter
from sys import exit
from decimal import *
import heapq
import math
from fractions import gcd
import random
import string
import copy
from itertools import combinations, permutations, product
from operator import mul
from functools import reduce
from bisect import bisect_left, bisect_right

import sys
sys.setrecursionlimit(1000000000)
mod = 10 ** 9 + 7






N, K = getNM()
P = [i - 1 for i in getList()]
C = getList()

ignore = [-1] * N
ans = -float('inf')
for i in range(N):
    if ignore[i] >= 0:
        continue
    
    ignore[i] = 1
    opt_l = [i]
    to = P[i]
    while ignore[to] == -1:
        opt_l.append(to)
        ignore[to] = 1
        to = P[to]
    
    
    n = len(opt_l)
    point = [0] * n
    for i in range(n):
        point[i] = C[opt_l[i]]
    
    
    sum_roop = sum(point)
    
    imos = [0]
    point += point
    for i in range(len(point)):
        imos.append(imos[i] + point[i])
    
    ran = min(n, K)
    for i in range(n):
        
        for j in range(1, ran + 1):
            if sum_roop >= 0:
                opt = imos[i + j] - imos[i] + ((K - j) // n) * sum_roop
            else:
                opt = imos[i + j] - imos[i]
            ans = max(ans, opt)
    
print(ans)

Solution (Python):
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ans=-10**18
flag=dict()
for i in range(n):
    if i in flag:
        continue
    cur=i
    accum=[]
    flag[cur]=0
    s=0
    while flag[cur]<2:
        cur=p[cur]-1
        s+=c[cur]
        accum.append(s)
        if cur not in flag:
            flag[cur]=0
        else:
            flag[cur]+=1
    l=len(accum)//2
    accum=[0]+accum
    
    for x in range(1,l+1):
        if accum[x+l-1]-accum[x-1]<=0 or k//l<1:
            ans=max(ans,max(accum[x:x+min(k,l)])-accum[x-1])
        else:
            a=max(accum[x:x+l-1])-accum[x-1]
            d=accum[x+l-1]-accum[x-1]
            if k%l!=0:
                b=max(accum[x:x+k%l])-accum[x-1]
                ans=max(ans,max(k//l*d,k//l*d+b,(k//l-1)*d+a))
            else:
                b=max(accum[x:x+l-1])-accum[x-1]
                ans=max(ans,max(k//l*d,(k//l-1)*d+a))
print(ans)

Solution (Python):

import itertools

if __name__ == "__main__":

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

	
	
	
	cycleIDs = [ -1 for _ in range(N)]
	cycleInfs = []
	cycleID = 0
	procCnt = 0

	for n in range(N):
		v = n

		if cycleIDs[v] != -1:
			continue
		else:
			currentCycleCosts = []
			while True:
				
				currentCycleCosts.append( C[v] )
				cycleIDs[v] = cycleID

				v = P[v]
				if cycleIDs[v] != -1:
					
					
					procCnt = K % len( currentCycleCosts )
					
					
					
					
					
					
					
					
					
					
					
					
					if len( currentCycleCosts ) + procCnt <= K:
						procCnt += len( currentCycleCosts )

					cycleInfs.append( ( procCnt, len(currentCycleCosts), currentCycleCosts * 3 ) )
					cycleID += 1
					break



	
	
	ans = -10 ** 9
	for procCnt, currentCycleSize, currentCycleCosts in cycleInfs:

		
		loopScore = 0
		if sum(currentCycleCosts) > 0:
			cycleLoopCnt =  ( K - procCnt ) // currentCycleSize
			loopScore = cycleLoopCnt * sum(currentCycleCosts[:currentCycleSize])
			

		
		for i in range(currentCycleSize):
			
			score = max( itertools.accumulate( currentCycleCosts[i:i+procCnt] ) )
			if ans < score + loopScore:
				ans = score + loopScore
			


	print(ans)

Solution (Python):
N, K = map(int, input().split())
p_list = list(map(int, input().split()))
c_list = list(map(int, input().split()))

max_score = 0
first = True
for i in range(N):
  score = 0
  step = 0
  path = {}
  cumulative_score = []
  current_p = i
  cycle_passed = False
  while step < K:
    
    cumulative_score.append(score)
    
    
    if (not cycle_passed) and (current_p in path.keys()):
      
      
      
      cycle_start_step = path[current_p]
      cycle_steps = step - cycle_start_step
      cycle_sum = cumulative_score[step] - cumulative_score[cycle_start_step]
      if cycle_sum < 0:
        
        
        break
      else:
        
        remain_steps = K - step
        if remain_steps > cycle_steps:
          cycle_times = (K - step) // cycle_steps - 1
          step += (cycle_times * cycle_steps)
          score += (cycle_times * cycle_sum)
          cycle_passed = True
        else:
          cycle_passed = True    
        
    
    path[current_p] = step
    
    
    next_p = p_list[current_p-1]
    score += c_list[next_p-1]
    if (first):
      max_score = score
      first = False
    else:
      max_score = max(max_score, score)
    
    current_p = next_p
    step += 1

print(max_score)

Solution (Python):
class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

N,K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
uf = UnionFind(N)
ans = -10**9
for i in range(N):
    uf.union(i,P[i]-1)
for group in uf.all_group_members().values():
    size = len(group)
    SUM = 0
    for i in group:
        SUM += C[i]
    if SUM < 0:
        SUM = 0
    for i in group:
        cur = i
        current_sum = 0
        remain = K
        for _ in range(size):
            cur = P[cur]-1
            current_sum += C[cur]
            remain -= 1
            if remain < 0:
                break
            ans = max(ans,current_sum+SUM*(remain//size))
print(ans)

Solution (Python):
from itertools import accumulate 

 
n, k = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
c = list(map(int, input().split()))
ans = -(10 ** 18)
 
for i in range(n):
    pos = i
    scores = []
    while True:
        pos = p[pos]
        scores.append(c[pos])
        if pos == i:
            break
    m = len(scores)
    s = list(accumulate(scores))
    for j in range(min(m, k)):
        x = (k - j - 1) // m
        ans = max(ans, s[j], s[j] + s[-1] * x)
 
print(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 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):
        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)