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):
from itertools import accumulate

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


Done = [False] * N
for i in range(N):
    if Done[i]:
        continue
    L = []
    now = i
    while True:
        L.append(C[now])
        Done[now] = True
        now = P[now] - 1
        if Done[now]:
            break
    Loop.append(L)
ans = - float('inf')
for L in Loop:
    B = [0] + list(accumulate(L + L))
    loop = K // len(L)
    rest = K % len(L)
    flag = False
    if loop > 0:
        flag = True
    ans1 = - float('inf')
    ans3 = - float('inf')
    for start in range(len(L)):
        for num in range(1, len(L)+1):
            end = start + num
            if end >= len(B):
                break
            if num <= rest:
                ans1 = max(ans1, B[end] - B[start])
            ans3 = max(ans3, B[end] - B[start])
    ans2 = max(0, loop * B[len(L)])
    ans4 = max(0, (loop - 1) * B[len(L)])
    ans = max(ans, ans1+ans2)
    if flag:
        ans = max(ans, ans3 + ans4)
print(ans)

Solution (Python):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
for k in range(N):
  P[k] -= 1
scorelist = []
roop = []
now = 0
visited = [-1 for _ in range(N)]
for k in range(N):
  now = k
  if visited[now] == -1:
    roop.append([])
    scorelist.append([])
    start = 0 + now
    while visited[start] == -1:
      roop[-1].append(start)
      visited[start] = 1 
      start = P[start]
      scorelist[-1].append(C[start])
    scorelist[-1] = scorelist[-1] + scorelist[-1] + scorelist[-1]
    



ans = - float('inf')
for l in range(len(roop)):
  
  Q = K // len(roop[l])
  R = K % len(roop[l])
  if Q > 0:
    Q -= 1
    R += len(roop[l]) 
  
  if sum(scorelist[l][:len(roop[l])]) > 0:
    basis = sum(scorelist[l][:len(roop[l])])*Q
  else:
    basis = 0
  
  advlist = -float('inf')
  for k in range(len(roop[l])):
    adv = 0
    for j in range(k, k + R):
      adv += scorelist[l][j]
      advlist  = max(advlist, adv) 
  ans = max(ans, basis + advlist)

print(ans)

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



def main():
    n, k = map(int, input().split())
    p = [int(x)-1 for x in input().split()]
    c = list(map(int, input().split()))
    
    doubling = [[0]*n for i in range(31)]
    doubling_max = [[0]*n for i in range(31)]
    place = [[0]*n for i in range(31)]
    
    ans = -1000000000
    for i in range(n):
        sub = c[p[i]]
        if sub >= 0:
            break
        if ans < sub:
            ans = sub
        if i == n-1:
            print(ans)
            sys.exit()
            
    
    for i in range(31):
        if i == 0:
            for j in range(n):
                doubling[i][j] = c[p[j]]
                place[i][j] = p[j]
            continue
        for j in range(n):
            place[i][j] = place[i-1][place[i-1][j]]
            doubling[i][j] = doubling[i-1][j]+doubling[i-1][place[i-1][j]]
    
    for i in range(31):
        if i == 0:
            for j in range(n):
                doubling_max[i][j] = doubling[i][j]
            continue
        for j in range(n):
            doubling_max[i][j] = max(doubling_max[i-1][j], doubling[i-1][j]+doubling_max[i-1][place[i-1][j]])
    
    ans = 0
    judge = []
    key = 0
    while k:
        if k%2:
            judge.append(key)
        k //= 2
        key += 1
    judge.reverse()
    
    for i in range(n):
        pl = i
        key = 0
        for j in range(len(judge)):
            if ans < key+doubling_max[judge[j]][pl]:
                ans = key+doubling_max[judge[j]][pl]
            key += doubling[judge[j]][pl]
            pl = place[judge[j]][pl]
        

    print(ans)
        
    


    
    
if __name__ == "__main__":
    main()

Solution (Python):
n,k=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):
  vis=set()
  now=i
  a=[0]
  m=k
  while m:
    vis.add(now)
    now=p[now]
    a+=[c[now]+a[-1]]
    m-=1
    if now in vis:break
  if m==0 or a[-1]<=0:
    cnt=max(a[1:])
  else:
    cnt=(k//(k-m))*a[-1]
    if k%(k-m):cnt+=max(a[1:k%(k-m)+1])
    elif max(a[1:])>a[-1]:
      cnt=cnt=(k//(k-m)-1)*a[-1]+max(a[1:])
  ans=max(ans,cnt)
print(ans)

Solution (Python):


import os,sys
from io import BytesIO, IOBase

def main():
    n,k = map(int,input().split())
    p = list(map(int,input().split()))
    c = list(map(int,input().split()))
    ans = -10**20
    for i in range(1,n+1):
        cou = 1
        se = {i}
        ne = p[i-1]
        su = [c[ne-1]]
        maxi = c[ne-1]
        while ne not in se and cou < k:
            se.add(ne)
            ne = p[ne-1]
            su.append(su[-1]+c[ne-1])
            maxi = max(maxi,su[-1])
            cou += 1
        if su[-1] > 0 and cou<k:
            maxi = max(maxi,su[-1]*(k//len(su))+max(su[:k%len(su)]+[-10**20]),su[-1]*(k//len(su)-1)+max(su))
        ans = max(ans,maxi)
    print(ans)


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")

if __name__ == '__main__':
    main()

Solution (Python):
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,k = list(map(int, input().split()))
p = list(map(lambda x: int(x)-1, input().split()))
c = list(map(int, input().split()))
seen = [None]*n
vs = []
ans = -float("inf")
def sub(v, num):
    if num==0:
        return 0
    v = v+v
    n = len(v)
    val = sum(v[:num])
    ans = val
    for i in range(num,n):
        val = val + v[i] - v[i-num]
        ans = max(ans, val)
    return ans
for i in range(n):
    if seen[i]:
        continue
    v = []
    s = i
    seen[s] = True
    while True:
        s = p[s]
        seen[s] = True
        v.append(c[s])
        if s==i:
            break
    ss =sum(v)
    val1 = -float("inf")
    if ss>=1 and k>=len(v):
        val1 = ss*(k//len(v))
        tmp = max(sub(v,i) for i in range((k%len(v))+1))
        val1 += tmp
        val0 = ss*(k//len(v)-1)
        val0 += max(sub(v,i) for i in range((len(v))+1))
        val1 = max(val0, val1)
    val2 = -float("inf")
    for i in range(1,min(k,len(v))+1):
        val2 = max(val2, sub(v, i))
        
    val = max(val1, val2)


    ans = max(ans, val)
print(ans)

Solution (Python):
from math import floor,ceil,sqrt
import fractions
from collections import deque
import itertools
import collections
from heapq import *

N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
suctable=[]
scoretable=[[0 for _ in range(N)] for _ in range(N)]
cyclesum=[]
for i in range(N):
    suctable.append(P[i]-1)
for i in range(N):
    
    suc=suctable[i]
    l=[0]*N
    flag=0
    l[suc]=1
    for j in range(N-1):
        scoretable[i][j+1]=scoretable[i][j]+C[suc]
        suc=suctable[suc]
        if (l[suc]==0)and(flag==0):
            l[suc]=1
        else:
            flag=1
    
    num=0
    num2=0
    for j in range(N):
        if l[j]==1:
            num=num+C[j]
            num2=num2+1
    cyclesum.append([num,num2])

ma=-float("inf")
K2=K
for i in range(N):
    
    K=K2
    if cyclesum[i][0]<=0:
        ma=max(ma,max(scoretable[i][1:(min(N,K+1))]))
    else:
        n=0
        if K<cyclesum[i][1]:
            n=max(scoretable[i][1:(min(N,K+1))])
        else:
            K=K-cyclesum[i][1]
            n=cyclesum[i][0] * (K // cyclesum[i][1])
            res=K%cyclesum[i][1]
            res=res+cyclesum[i][1]
            
            suc=suctable[i]
            for _ in range(res):
                n=n+C[suc]
                ma=max(ma,n)
                suc=suctable[suc]
                
            
        ma=max(ma,n)
print(ma)

Solution (Python):
import math

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


cycle_scores = [None]*N
cycle_lengths = [None]*N

for x in range(N):
    if cycle_scores[x] is not None: continue

    cycle = []
    i = x
    score = 0
    while True:
        i = P[i]
        score += C[i]
        cycle.append(i)
        if i == x: break

    for i in cycle:
        
        cycle_scores[i] = score
        cycle_lengths[i] = len(cycle)

best = -math.inf
for x in range(N):
    fuel = K
    i = x
    partial = 0
    for _ in range(min(K, cycle_lengths[x])):
        i = P[i]
        fuel -= 1
        partial += C[i]
        if cycle_scores[i] > 0 and fuel >= cycle_lengths[i]:
            score = partial + cycle_scores[i] * (fuel // cycle_lengths[i])
        else:
            score = partial
        best = max(best, score)

print(best)

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

max_score = -10 ** 9
for i in range(N):
    memo = set()
    score = 0
    cur = i
    move = 0

    while move < K and P[cur] not in memo:
        cur = P[cur]
        memo.add(cur)
        score += C[cur]
        move += 1
        max_score = max(score, max_score)

    if move < K and score > 0:
        score = max(K // move - 1, 1) * score
        move *= max(K // move - 1, 1)
        max_score = max(score, max_score)

        cur = i
        while move < K:
            cur = P[cur]
            score += C[cur]
            move += 1
            max_score = max(score, max_score)

print(max_score)

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

roop_count = [1] * N
roop_score = [0] * N
step_score = [[] for i in range(N)]

for i in range(N):
    start_p = i
    next_p = P[i] - 1
    roop_score[i] = C[i]
    step_score[i].append(roop_score[i])
    while start_p != next_p:
        p = next_p
        next_p = P[p] - 1
        roop_score[i] = roop_score[i] + C[p]
        roop_count[i] = roop_count[i] + 1
        step_score[i].append(roop_score[i])

max_score = [0] * N

for i in range(N):
    if K > roop_count[i] and roop_score[i] > 0:
        k = K // roop_count[i]
        e = K % roop_count[i]
        for j in range(e):
            step_score[i][j] = step_score[i][j] + roop_score[i]
        for j in range(roop_count[i]):
            step_score[i][j] = step_score[i][j] + roop_score[i] * (k - 1)
    if K >= roop_count[i]:
        max_score[i] = max(step_score[i])
    else:
        max_score[i] = max(step_score[i][:K])

print(max(max_score))

Solution (Python):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -1000000000
for i in range(N):
  cost = 0
  S = []
  x = P[i] - 1
  l = 1
  while 1:
    cost += C[x]
    S.append(cost)
    if x == i:
      break
    l += 1
    x = P[x] - 1
  if cost > 0:
    for j in range(l):
      ans = max(ans, S[j] + cost * ((K - j - 1) // l))
  else:
    ans = max(ans, max(S[:min(K, l)]))
print(ans)

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

l = []

todo = [0] * n
for i in range(n):
    if todo[i] == 1:
        continue
    todo[i] = 1
    lis = [c[i]]
    now = p[i]
    while todo[now] == 0:
        todo[now] = 1
        lis.append(c[now])
        now = p[now]
    l.append(lis)

ans = -float('inf')
for i in l:
    s = [i[0]]
    for j in range(1, len(i)):
        s.append(s[-1] + i[j])
    unit = s[-1]
    for j in range(len(i)):
        s.append(s[-1] + i[j])
    for j in range(len(i)):
        s.append(s[-1] + i[j])

    num = k
    if s[-1] > 0:
        if num // len(i) > 1:
            score = (num // len(i) - 1) * unit
            num %= len(i)
            num += len(i)
        else:
            score = 0
    else:
        score = 0
        num = len(i)
    
    for a in range(len(i)):
        for b in range(a + 1, a + num + 1):
            if score + s[b] - s[a] > ans:
                ans = score + s[b] - s[a]

print(ans)

Solution (Python):
N,K=map(int,input().split())
P=list(map(int,input().split()))
C=list(map(int,input().split()))
a=[]
ans=-10**10
for i in range(N):
    idx=P[i]-1
    z=set()
    rl=[]
    c=0
    tc=0
    while idx not in z and c<K:
        tc+=C[idx]
        rl.append(tc)
        ans=max(ans,tc)
        z.add(idx)
        idx=P[idx]-1
        c+=1
    if c<K:
        d,m=divmod(K,c)
        if m==0:
            d-=1
            m=c
        tc=d*tc
        tc+=max(rl[:m])
        ans=max(ans,tc)
print(ans)

Solution (Python):
import bisect, copy, heapq, math, sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
def celi(a,b):
    return -(-a//b)
sys.setrecursionlimit(5000000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

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

dic_s={}
dic_i={}

for i in range(1,n+1):
    if not i in dic_i:
        dic_s[i]=0
        j=i
        while not j in dic_i:
            dic_i[j]=1
            j=p[j-1]
            dic_s[i]+=1

ans=-float('inf')
for i in dic_s.keys():
    lst_c=[]
    
    for j in range(dic_s[i]):
        i=p[i-1]
        lst_c.append(c[i-1])
    
    
    
    sm=sum(lst_c)
    lst=lst_c+lst_c+lst_c
    if sm>0:
        cnt2=-float('inf')
        if k//dic_s[i]>=2:
            for j in range(dic_s[i]):
                tmp=0
                for l in range(k%dic_s[i]+dic_s[i]):
                    tmp+=lst[j+l]
                    cnt2=max(cnt2,tmp)
        ans=max(ans,sm*(k//dic_s[i]-1)+cnt2)
        cnt2=-float('inf')
        for j in range(dic_s[i]):
            tmp=0
            for l in range(k%dic_s[i]):
                tmp+=lst[j+l]
                cnt2=max(cnt2,tmp)
        ans=max(ans,sm*(k//dic_s[i])+cnt2)

    
        
    cnt2=-float('inf')
    for j in range(dic_s[i]):
        tmp=0
        for l in range(min(k,dic_s[i])):
            tmp+=lst[j+l]
            cnt2=max(cnt2,tmp)
        
    ans=max(ans,cnt2)

print(ans)

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

ans = min(C)
for i in range(N):
  s = 0
  m = [0 for i in range(N+1)]
  t = i
  step = 0
  while step < K:
    step += 1
    t = P[t] - 1
    s += C[t]
    m[step-1] = s
    if t == i:
      break
  
  
  for j in range(step):
    ans = max(ans, m[j])
  
  if K % step == 0 and s > 0:
    mod_max = 0
    for j in range(step):
      mod_max = max(mod_max, m[j])
    ans = max(ans, mod_max + max(s, 0) * ((K // step)-1))
  elif s > 0:
    mod_max = 0
    for j in range(K % step):
      mod_max = max(mod_max, m[j])
    ans = max(ans, mod_max + max(s, 0) * (K // step))

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()]

ret = -float('inf')
done = set()
for n in range(N) :
  if n in done : continue
    
  cur = n
  s = C[cur]
  done.add(cur)
  loop = [n]
  while not P[cur] in done :
    cur = P[cur]
    done.add(cur)
    loop.append(cur)
    s += C[cur]
  
  if s <= 0:
    for i in loop :
      cur = i
      x = 0
      for _ in range(min(len(loop), K)) :
        cur = P[cur]
        x += C[cur]
        ret = max(ret, x)
  else :
    d = 0
    k = K
    if k > len(loop) :
      d = s * (k // len(loop) - 1)
      k = k % len(loop) + len(loop)
      
    for i in loop :
      cur = i
      x = 0
      for _ in range(k) :
        cur = P[cur]
        x += C[cur]
        ret = max(ret, x + d)
      
print(ret)

Solution (Python):
import sys

sys.setrecursionlimit(10**6)
input = sys.stdin.readline

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

    ans = -float('inf')
    for n in range(N):
        m = n
        ans_tmp = 0
        cnt = 0
        repeat_flag = False
        for k in range(K):
            nxt = P[m]
            score = C[nxt-1]
            ans_tmp += score
            ans = max(ans, ans_tmp)
            m = nxt-1
            cnt += 1
            if m == n:
                repeat_flag = True
                break
        if not repeat_flag:
            continue
        if K%cnt == 0:
            divK = K//cnt - 1
            r = cnt
        else:
            divK = K//cnt
            r = K%cnt
        if ans_tmp <= 0:
            continue
        repeat_ans_tmp = ans_tmp * divK
        for k in range(r):
            nxt = P[m]
            score = C[nxt-1]
            repeat_ans_tmp += score
            ans = max(ans, repeat_ans_tmp)
            m = nxt-1

    print(ans)


if __name__ == "__main__":
    main()

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

P = [p-1 for p in P]

D = [[-10**18]*(n+1) for _ in range(n)]
for i in range(n):
    D[i][0] = 0
Q = [0]*n
A = [0]*n
for i in range(n):
    pos = i
    for j in range(n):
        D[i][j+1] = C[P[pos]]+D[i][j]
        pos = P[pos]
        if pos == i:
            break
    Q[i] = D[i][j+1]
    A[i] = j+1





ans = -10**18

for i in range(n):
    if k < A[i]:
        for j in range(k):
            ans = max(D[i][j+1], ans)
    else:
        if D[i][0] > Q[i]:
            for j in range(A[i]):
                ans = max(D[i][j+1], ans)
        else:
            q, r = divmod(k, A[i])
            temp = (q-1)*Q[i]
            if q-1 != 0:
                ans = max(temp, ans)
            for j in range(A[i]):
                ans = max(D[i][j+1]+temp, ans)
            temp = q*Q[i]
            ans = max(temp, ans)
            for j in range(r+1):
                ans = max(D[i][j]+temp, ans)

print(ans)

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

table=[0]*N
ans=-float("INF")
for i in range(N):
    L=[]
    count=0
    score=0
    max_score=-float("INF")
    now=i+1
    while count<K:
        now=P[now-1]
        add=C[now-1]
        score+=add
        max_score=max(score, max_score)
        L.append(add)
        count+=1
        if now==i+1:
            break
    
    if sum(L)>0 and now==i+1:
        max_score=sum(L)*((K-count)//count)
        res=count+K%count
        score=max_score
        
        
        while res>0:
            now=P[now-1]
            add=C[now-1]
            score+=add
            max_score=max(score, max_score)
            res-=1
            
        
    
    
    
    
    
    ans=max(ans, max_score)
    
print(ans)

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

ans = -(10 ** 15)
for i in range(N):
    kans = 0
    score = [0]
    nex = P[i] -1
    while True:
        score.append(score[-1] + C[nex])
        nex = P[nex] - 1
        if nex == P[i] -1:
            break;

    if score[-1] > 0:
        if score[1:(K % (len(score) -1)) + 1] != []:
            kans = score[-1] * (K // (len(score) -1)) + max(score[1:(K % (len(score) -1)) + 1])
        else:
            kans = score[-1] * ((K // (len(score) -1)) - 1) + max(score)
    else:
        if score[1:min(len(score) - 1,K) + 1] != []:
            kans = max(score[1:min(len(score) - 1,K) + 1])
        else:
            kans = -(10 ** 15)
    ans = max(ans,kans)
print(ans)

Solution (Python):
N, K = [int(i) for i in input().split()]
ps = [int(i) for i in input().split()]
cs = [int(i) for i in input().split()]

global_max = -10**10
past_score = [[]]*N
past_time = [[]]*N
for n in range(N):
    score = 0
    itta = [0]*N
    iru = n
    k = 0
    while k < K:
        score += cs[ps[iru]-1]
        k += 1
        if itta[iru] == 1:
            
            
            
            
            if score > past_score[iru]:
                
                T = k - past_time[iru]  
                
                if K - k > (2 * T) + 1:
                    
                    
                    score += (((K-k)//T - 1)*(score - past_score[iru]))
                    k += T * ((K-k)//T - 1)
                    
                    
            else:
                
                break
        itta[iru] = 1
        
        
        
        global_max = max(score, global_max)
        past_score[iru] = score
        past_time[iru] = k
        iru = ps[iru]-1
print(global_max)

Solution (Python):
from collections import defaultdict

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



x = 0
used = [0] * N
path = defaultdict(list)
score = defaultdict(list)
for i in range(N):
    if used[i]:
        continue
    x = i
    while used[x] == 0:
        used[x] = 1
        path[i].append(x)
        score[i].append(C[x])
        x = P[x]
ans = -float('inf')
for r in path:
    pa, sc, le = path[r], score[r], len(path[r])
    
    for i in range(le-1):
        sc[i+1] += sc[i]
    
    if sc[-1] <= 0 or K < le:
        m = -float('inf')
        for i in range(len(pa)):
            for j in range(i+1, len(pa)):
                if j - i <= K:
                    m = max(m, sc[j] - sc[i])
                if le - j + i <= K:
                    m = max(m, sc[-1] - sc[j] + sc[i])
        ans = max(ans, m)
    else:
        k = K % le
        m = 0 if k == 0 else -float('inf')
        for i in range(le):
            for j in range(i+1, le):
                if j - i <= k:
                    m = max(m, sc[j] - sc[i])
                if le - j + i <= k:
                    m = max(m, sc[-1] - sc[j] + sc[i])
        ans = max(ans, m + sc[-1] * (K // le))

        m = -float('inf')
        for i in range(le):
            for j in range(i+1, le):
                if j - i <= le:
                    m = max(m, sc[j] - sc[i])
                if le - j + i <= le:
                    m = max(m, sc[-1] - sc[j] + sc[i])
        ans = max(ans, m + sc[-1] * ((K // le) - 1))
print(ans)

Solution (Python):
'''
    Auther: ghoshashis545 Ashis Ghosh
    College: jalpaiguri Govt Enggineering College

'''
from os import path
import sys
from functools import cmp_to_key as ctk
from collections import deque,defaultdict as dd 
from bisect import bisect,bisect_left,bisect_right,insort,insort_left,insort_right
from itertools import permutations
from datetime import datetime
from math import ceil,sqrt,log,gcd
def ii():return int(input())
def si():return input()
def mi():return map(int,input().split())
def li():return list(mi())
abc='abcdefghijklmnopqrstuvwxyz'
mod=1000000007

inf = float("inf")
vow=['a','e','i','o','u']
dx,dy=[-1,1,0,0],[0,0,1,-1]

def bo(i):
    return ord(i)-ord('a')


def fun(x,k):
    ans = -inf
    x += x
    n = len(x)
    for i in range(1,k+1):
        s = 0
        for j in range(i):
            s += x[j]
        l = 0
        ans = max(ans,s)
        for j in range(i,n):
            s += x[j]
            s -= x[l]
            l += 1
            ans = max(ans,s)
    return ans 



def solve():
    
    

        


    n,k = mi()
    p = li()
    c = li()

    vis = [0]*(n+1)
    a = []
    for i in range(n):
        if vis[i]:
            continue
        x = []
        j = i
        while(vis[j]==0):
            vis[j] = 1
            x.append(c[p[j]-1])
            j = p[j]-1
        a.append(x)
    

    ans = -inf

    for i in a:
        s = sum(i)
        n = len(i)
        k1 = k
        if(k >= n):
            k1 = n 
        s1 = fun(i,k1)
        ans = max(ans,s1)
        if(k > n and s>0):
            s2 = (k//n)*s
            s2 += fun(i,k%n)
            ans = max(ans,s2)
            ans = max(ans,s1+(k//n-1)*s)
        ans = max(ans,s1)

    print(ans)
















        
if __name__ =="__main__":

    if path.exists('input.txt'):
        sys.stdin=open('input.txt', 'r')
        sys.stdout=open('output.txt','w')
    else:
        input=sys.stdin.readline
    solve()

Solution (Python):
import sys
stdin = sys.stdin
sys.setrecursionlimit(10**6)
ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
nn = lambda: list(stdin.readline().split())
ns = lambda: stdin.readline().rstrip()

n,k = na()
p = na()
c = na()

s = set(range(n))

ans = 0
loops = []
while s:
    loop = [0]
    a = s.pop()
    while True:
        loop.append(loop[-1]+c[p[a]-1])
        if p[a]-1 not in s:
            break
        a = p[a]-1
        s.discard(a)
    loops.append(loop[1:])

ans = -1000000000000000
for tmp in loops:
    kk = k
    if k > len(tmp): kk = k%len(tmp)+len(tmp)
    loop = [0]+tmp+[tmp[-1]+u for u in tmp]+[tmp[-1]*2+u for u in tmp]
    x = -1000000000000
    for i in range(1,kk+1):
        for j in range(len(tmp)+1):
            x = max(x,loop[j+i]-loop[j])
    if k > len(tmp) and tmp[-1] > 0:
        x += tmp[-1]*(k//len(tmp)-1)
    ans = max(ans,x)

print(ans)

Solution (Python):
from itertools import accumulate


def solve(n, k, ppp, ccc):
    NINF = -(10 ** 18)
    ans = NINF

    checked = [False] * n
    for s in range(n):
        if checked[s] == True:
            continue
        checked[s] = True
        scores = [ccc[ppp[s]]]
        starts = [s]
        v = ppp[s]
        while v != s:
            scores.append(ccc[ppp[v]])
            starts.append(v)
            checked[v] = True
            v = ppp[v]

        l = len(scores)
        d, m = divmod(k, l)
        loop = sum(scores)

        if d > 0:
            d -= 1
            m += l

        base = max(0, loop * d)

        for s in starts:
            v = ppp[s]
            score = base + ccc[ppp[s]]
            best_score = score
            for _ in range(m - 1):
                score += ccc[ppp[v]]
                v = ppp[v]
                best_score = max(best_score, score)
            ans = max(ans, best_score)

    return ans


n, k = map(int, input().split())
ppp = list(map(int, input().split()))
ppp = [p - 1 for p in ppp]
ccc = list(map(int, input().split()))

print(solve(n, k, ppp, ccc))

Solution (Python):
n,k=map(int, input().split())
P = list(map(int, input().split()))
P=[i-1 for i in P]
C = list(map(int, input().split()))
visited=[-1]*n
group=[]

for i in range(n):
    if visited[i]!=-1:
        continue
    visited[i]=0
    group.append([i])
    now=P[i]
    while now!=i:
        group[-1].append(now)
        visited[now]=0
        now=P[now]
dp=[[0] for i in range(n)]

from collections import defaultdict
d=defaultdict(list)
for g in group:
    for i in g:
        now=i
        point=0
        for j in range(len(g)):
            now=P[now]
            point+=C[now]
            d[i].append(point)
ans=-float('inf')

for i in range(n):
    dic=d[i]
    leng=len(dic)
    if k<=leng:
        ans=max(ans, max(dic[:k]))
    else:
        if dic[-1]<=0:
            ans=max(ans, max(dic))
        else:
            if k%leng!=0:
                ans=max(ans,(k//leng)*dic[-1]+max(dic[:k%leng]))
            ans=max(ans,(k//leng-1)*dic[-1]+max(dic))
print(ans)