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, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
point_start_with = [0 for i in range(n)]
roop_count = [1 for i in range(n)]
for i in range(n):
    now = (i + 1)
    now_score = 0
    while p[now - 1] != (i + 1):
        now = p[now - 1]
        now_score += c[now - 1]
        roop_count[i] += 1
    point_start_with[i] = now_score

ans = -(10**9 * 5000)
for i in range(n):
    
    score = 0
    remain_move = 0
    cand_score = 0
    if point_start_with[i] + c[i] > 0 and k > roop_count[i]:
        
        
        
        round_count = (k // roop_count[i]) - 1
        remain_move = k - round_count * roop_count[i]
        cand_score = round_count * ( point_start_with[i] + c[i] )
    else:
        remain_move = min(k,roop_count[i])
        score = -(10**9 * 5000)
        cand_score = 0
    now = i
    for j in range(remain_move):
        now = p[now] - 1
        cand_score += c[now]
        score = max(score, cand_score)
    
    ans = max(score, ans)
print(ans)

Solution (Python):

par = {}
sum_union = {}
len_union = {}


def init(n):
  for i in range(n):
    par[i] = i
    sum_union[i] = Cs[i]
    len_union[i] = 1
  return 
  

def root(x):
  if par[x] == x:
    return x
  else:
    
    par[x] = root(par[x])
    return par[x]


def same(x, y):
  return root(x) == root(y)


def unite(x, y):
  rx = root(x)
  ry = root(y)
  if rx == ry:
    return
  else:
    par[rx] = ry
    tmp_sum = sum_union[rx] + sum_union[ry]
    tmp_len = len_union[rx] + len_union[ry]
    sum_union[ry] = tmp_sum
    len_union[ry] = tmp_len
    return
  
N, K = map(int, input().split())
Ps = list(map(lambda x: int(x) - 1, input().split()))
Cs = list(map(int, input().split()))


init(N)


for i in range(N):
  unite(i, Ps[i])
  
max_result = -(10**9+1)
for i in range(N):
  ri = root(i)
  if sum_union[ri] <= 0:
    partial_range = min(K, len_union[ri])
    roop_sum = 0
  elif K < len_union[ri]:
    partial_range = K
    roop_sum = 0
  else:
    partial_range = (K % len_union[ri]) + len_union[ri]
    roop_sum = sum_union[ri] * ((K // len_union[ri])-1)
  pc = i
  sum_list = []
  sum_c = 0
  for _ in range(partial_range):
    pn = Ps[pc]
    sum_c += Cs[pn]
    sum_list.append(sum_c)
    pc = pn
    
  max_result = max(max_result, roop_sum + max(sum_list))
  
print(max_result)

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

c_list = []
rink_list = []
visited = set()
ans = -10 ** 10
for i in range(n):
    sum_c = c[i]
    j = p[i] - 1
    num = 1
    while i != j:
        sum_c += c[j]
        j = p[j] - 1
        num += 1

    sum_c = max(0, sum_c)
    
    cnt = 1
    j = p[i] - 1
    tmp = c[i]
    ans = max(ans, tmp + sum_c * ((k - cnt) // num))
    while cnt < k and i != j:
        cnt += 1
        tmp += c[j]

        ans = max(ans, tmp + sum_c * ((k - cnt) // num))
        j = p[j] - 1

if ans == 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()))
assert len(p) == len(c) == n

visited = [False] * n
scc = []
for i in range(n):
    if not visited[i]:
        scc.append([])
        j = i
        while not visited[j]:
            visited[j] = True
            scc[-1].append(j)
            j = p[j] - 1

n_scc = len(scc)
subsum = [[0] for i in range(n_scc)]
for i in range(n_scc):
    for j in scc[i]:
        subsum[i].append(subsum[i][-1] + c[j])
    for j in scc[i]:
        subsum[i].append(subsum[i][-1] + c[j])

def lister(k):
    for i in range(n_scc):
        l = len(scc[i])
        loop_score = max(0, subsum[i][l])
        for kk in range(1, min(k, l) + 1):
            base = loop_score * ((k - kk) // l)
            for j in range(kk, l + kk + 1):
                yield base + subsum[i][j] - subsum[i][j - kk]

print(max(lister(k)))

Solution (Python):

printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True 
BIG = 10**18+7
R = 10**9 + 7


def ddprint(x):
  if DBG:
    print(x)

n,k = inm()
p = inl()
c = inl()
p = [x-1 for x in p]
used = [False]*n
mx = -BIG
for i in range(n):
    if used[i]:
        continue
    j = p[i]
    used[i] = used[j] = True
    pt = c[j]
    ids = [i,j]
    acc = [0,pt]
    while j!=i:
        j = p[j]
        used[j] = True
        pt += c[j]
        ids.append(j)
        acc.append(pt)
    ids.pop()
    cycsum = acc[-1]
    t = len(ids)
    if k>=t:
        mx = max(mx, cycsum*(k//t))
        mx = max(mx, cycsum)
    for j in range(1,t):
        acc.append(acc[j]+cycsum)
    
    for j in range(t):
        for m in range(1,min(k+1,t)):
            mx = max(mx, acc[j+m]-acc[j]+max(0,cycsum*((k-m)//t)))
print(mx)

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

ans = -(10**9+1)
for i in range(n):
  s = 0
  x = i
  for j in range(k):
    x = p[x]
    s += c[x]
    ans = max(ans,s)
    if i == x:
      break
  a = int(k/(j+1))
  m = k%(j+1)
  if m == 0 and a > 1:
    m = j+1
    a -= 1
  s *= a
  ans = max(ans,s)
  for l in range(m):
    x = p[x]
    s += c[x]
    ans = max(ans, s)
print (ans)

Solution (Python):
N, K = map(int, input().split())
Ps = list(map(int, input().split()))
Ps = [i - 1 for i in Ps]
Cs = list(map(int, input().split()))
max_score = -float("inf")


for i in range(N):
    scores = []
    idx = i  
    while True:
        idx = Ps[idx]  
        scores.append(Cs[idx])  
        if idx == i:  
            break

    len_cycle = len(scores)
    sum_cycle = sum(scores)

    if sum_cycle <= 0:  
        score = 0
        for j in range(min(K, len_cycle)):
            score += scores[j]
            max_score = max(max_score, score)
    else:
        if K // len_cycle > 0:
            num_multiply = K // len_cycle - 1
            score = sum_cycle * num_multiply
            scores = scores * 2
            for j in range(K % len_cycle + len_cycle):
                score += scores[j]
                max_score = max(max_score, score)
        else:
            num_multiply = 0  
            score = sum_cycle * num_multiply
            for j in range(K):
                score += scores[j]
                max_score = max(max_score, score)

print(max_score)

Solution (Python):



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



ans = -99999999999999

for i in range(N):
    x = i
    total = 0
    s=[]
    while(1):
        x = P[x]-1
        s.append(C[x])
        total += C[x]
        if x == i:
            break
    l = len(s)
    t = 0
    for i in range(l):
        t += s[i]
        if i+1> K:
            break
        now = t
        if total > 0:
            cycle = int((K-i-1)/l)
            now += total*cycle

        ans = max(ans, now)

print(ans)

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

def main():
  ans=-float('inf')
  for si in range(n):
    x=si
    S=[]
    tot=0
    while True:
      x=P[x]
      S.append(C[x])
      tot+=C[x]
      if x==si:
        break
    l=len(S)
    t=0
    for i in range(l):
      t+=S[i]
      if i+1>k:
        break
      now=t
      if tot>0:
        e=(k-i-1)//l
        now+=tot*e
      ans=max(ans,now)
  return ans      


if __name__=='__main__':
  print(main())

Solution (Python):

import sys
sys.setrecursionlimit(10**8)
from bisect import bisect_left
from itertools import product
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x)-1, input().split()))
def LF(): return list(map(float, input().split()))
def LC(): return [c for c in input().split()]
def LLI(n): return [LI() for _ in range(n)]
def NSTR(n): return [input() for _ in range(n)]

def array2d(N, M, initial=0):
    return [[initial]*M for _ in range(N)]

def copy2d(orig, N, M):
    ret = array2d(N, M)
    for i in range(N):
        for j in range(M):
            ret[i][j] = orig[i][j]
    return ret


INF = float("inf")
MOD = 10**9 + 7


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

    
    
    ans = -INF
    for i in range(N):
        v = i
        cycle_sum = 0
        cycle_cnt = 0

        
        while True:
            cycle_cnt += 1
            cycle_sum += C[v]
            v = P[v]
            if v == i:
                break

        path = 0
        cnt = 0

        while True:
            cnt += 1
            path += C[v]
            if cnt > K:
                break

            
            num = (K-cnt)//cycle_cnt
            score = path + max(0, cycle_sum)*num
            ans = max(ans, score)

            v = P[v]
            if v == i:
                break

    print(ans)
    return


if __name__ == '__main__':
    main()

Solution (Python):




def main():
  n, k = map(int, input().strip().split())
  lp = list(map(lambda p:int(p)-1, input().strip().split()))
  lc = list(map(int, input().strip().split()))

  used = [0] * n
  loops = []
  for i in range(n):
    if used[i] == 1:
      continue
      
    ic = i
    loop = []
    while used[ic] == 0:
      loop.append(lc[ic])
      used[ic] = 1      
      ic = lp[ic]
      
    if len(loop) > 0:
      loops.append(loop)
    
  def loop_score(loop, k):
    return (k // len(loop)) * sum(loop)
  
  def path_score(loop, k):
    score = 0
    for i in range(len(loop)):
      cumsum = 0
      for j in range(k):
        cumsum += loop[(i+j) % len(loop)]
        score = max(score, cumsum)
    return score
  
  def calc_score(loop, k):
    if max(loop) < 0:
      return max(loop)
    
    if k < len(loop):
      return path_score(loop, k)
    if k >= len(loop):
      k -= len(loop)
      score = 0
      if sum(loop) > 0:
        score += loop_score(loop, k)
      k %= len(loop)
      k += len(loop)
      score += path_score(loop, k)

    return score
  
  print(max([calc_score(loop, k) for loop in loops]))

if __name__=='__main__':
  main()

Solution (Python):
import math

class doubling:
    def __init__(self, seni, max_jump, reward = None):
        self.depth = math.ceil(math.log2(max_jump))
        self.N = len(seni)
        self.jumps = [[0 for i in range(self.N)] for _ in range(self.depth+1)]
        self.jumps[0] = seni
        
        if reward:
            self.rewards = [[0 for i in range(self.N)] for _ in range(self.depth+1)]
            self.rewards[0] = reward
            
        for i in range(self.depth):
            for j in range(self.N):
                self.jumps[i+1][j] = self.jumps[i][self.jumps[i][j]]
                if reward:
                    self.rewards[i+1][j] = self.rewards[i][j] + self.rewards[i][self.jumps[i][j]]
    def calculation(self, now, move):
        count = move.bit_length()
        reward = 0
        for i in range(count):
            if move & 1<<i == 1<<i:
                if self.rewards:
                    reward += self.rewards[i][now]
                now = self.jumps[i][now]
        return now, reward


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


answer = -int(1e+50)

if K < N:
    minimum = K
else:
    minimum = N

for i in range(N):
    now2, reward2 = i, 0
    for j in range(minimum):
        reward2 = reward2 + C[now2]
        now2 = P[now2]
        if reward2 > answer:
            answer = reward2

consume = K-N
if consume > 0:
    dbl = doubling(P, consume, C)
    for i in range(N):
        now1, reward1 = dbl.calculation(i, consume)
        for j in range(N):
            reward1 = reward1 + C[now1]
            now1 = P[now1]
            if reward1 > answer:
                answer = reward1
print(answer)

Solution (Python):
n, k = map(int, input().split())
positions = [int(i) for i in input().split()]
scores = [int(i) for i in input().split()]
if max(scores) <= 0:
  print(max(scores))
else:
  positions = [0] + positions
  scores = [0] + scores
  max_point = -pow(10, 9)
  
  dic = {}
  for i in range(1, n + 1):
    f_pos = i
    
    if f_pos not in dic:
      point_loop = 0
      loop = 0
      pos_set = set([f_pos])
      while True:
        f_pos = positions[f_pos]
        point_loop += scores[f_pos]
        
        
        loop += 1
        if f_pos in pos_set:
          for j in pos_set:
            dic[j] = [loop, point_loop]
          break
        pos_set.add(f_pos)
    else:
      loop, point_loop = dic[f_pos]
    
    loop_c = k // loop
    r = k % loop
    if loop_c == 0 or point_loop <= 0:
      if point_loop <= 0:
        if loop_c > 0:
          r = loop
      point = 0
      for _ in range(r):
        f_pos = positions[f_pos]
        point += scores[f_pos]
        max_point = max(max_point, point)
    else:
      point1, point2 = 0, 0
      point1 = loop_c * point_loop
      max_point1 = point1
      for _ in range(r):
        f_pos = positions[f_pos]
        point1 += scores[f_pos]
        max_point1 = max(point1, max_point1)
      f_pos = i
      point2 = (loop_c - 1) * point_loop
      max_point2 = point2
      for _ in range(loop):
        f_pos = positions[f_pos]
        point2 += scores[f_pos]
        max_point2 = max(point2, max_point2)
      max_point = max(max_point, max(max_point1, max_point2))
  print(max_point)

Solution (Python):
n, k = map(int, input().split())
positions = [int(i) for i in input().split()]
scores = [int(i) for i in input().split()]
if max(scores) <= 0:
  print(max(scores))
else:
  positions = [0] + positions
  scores = [0] + scores
  max_point = -pow(10, 9)
  
  for i in range(1, n + 1):
    s = []
    f_pos = positions[i]
    score = scores[f_pos]
    s.append(score)
    while f_pos != i:
      f_pos = positions[f_pos]
      score += scores[f_pos]
      s.append(score)
    loop = len(s)
    if loop >= k:
      point = max(s[:k])
    elif s[-1] <= 0:
      point = max(s)
    else:
      loop_c = k // loop
      r = k % loop
      point1 = s[-1] * loop_c
      if r != 0:
        point1 += max(s[:r])
      point2 = s[-1] * (loop_c - 1)
      point2 += max(0, max(s))
      point = max(point1, point2)
    max_point = max(max_point, point)
  print(max_point)

Solution (Python):
N,K = map(int,input().split())
P = [0]+list(map(int,input().split()))
C = [0]+list(map(int,input().split()))
ans = -float("INF")
for i in range(1,N+1):
    scores = [None]*(N+1)
    steps = [None]*(N+1)
    score = 0
    step = 0
    cur = i
    while step <= K:
        if step != 0:
            ans = max(ans,score)
        if step <= N:
            scores[cur] = score
            steps[cur] = step
        else:
            if scores[cur] >= score:
                
                break
            else:
                
                loopStep = step-steps[cur]
                loopScore = score-scores[cur]
                restLoop = (K-step)//loopStep
                if restLoop > 0:
                    restLoop -= 1
                step += restLoop*loopStep
                score += restLoop*loopScore
                scores[cur] = score
                steps[cur] = step
        step += 1
        cur = P[cur]
        score += C[cur]
print(ans)

Solution (Python):
N, K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
S = []
R = -1000000001

for i in range(N):
    t = i  
    cnt = 0  
    sum = []  
    res = 0
    while True:
        t = P[t]-1
        cnt += C[t]
        sum.append(cnt)
        if t == i:
            break
    
    if len(sum) >=  K:
        res = max(sum[:K])
    else:
        if sum[-1] <= 0:
            res = max(sum)
        else:
            score1 = sum[-1] * (K // len(sum) - 1) + max(sum)
            score2 = sum[-1] * (K // len(sum))
            r = K % len(sum)
            if r != 0:
                score2 += max(0, max(sum[:r]))
            res = max(score1,score2)
    R = max(R,res)
print(R)

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)

Solution (Python):
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
ttl=[]
cnt=[]
count=0
for i in range(n):
  nxt=i+1
  grp=[]
  count=0
  pnt=[]
  pnt.append(0)
  for j in range(n):
    nxt=p[nxt-1]
    pnt.append(pnt[j]+c[nxt-1])
    count+=1
    if nxt==i+1:
      del pnt[0]
      ttl.append(pnt)
      cnt.append(count)
      break
ans=[]
for i in range(n):
  peak=ttl[i].index(max(ttl[i]))
  if k<=cnt[i]:
    ans.append(max(ttl[i][:k]))
  else:
    if ttl[i][-1]<0:
      ans.append(ttl[i][peak])
    else:
      if k%cnt[i]==0:
        ans.append(((k-peak-1)//cnt[i])*ttl[i][-1]+ttl[i][peak])
      else:
        ans.append(max((k//cnt[i])*ttl[i][-1]+max(ttl[i][0:k%cnt[i]]),((k-peak-1)//cnt[i])*ttl[i][-1]+ttl[i][peak]))
print(max(ans))

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

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

    def connect(self, x, y):
        x = self.root(x)
        y = self.root(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 isConnect(self, x):
        return self.root(x) == self.root(y)

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

def solve():
    N, K = map(int, input().split())
    P = list(map(lambda x: int(x) - 1, input().split()))
    C = list(map(int, input().split()))
    INF = 10 ** 18
    dp = [[-INF] * (N + 1) for i in range(N)]
    ans = -INF
    uf = Unionfind(N)
    for i in range(N):
        dp[i][0] = 0
        now = i
        for j in range(min(N, K)):
            now = P[now]
            uf.connect(i, now)
            dp[i][j + 1] = dp[i][j] + C[now]
            ans = max(ans, dp[i][j + 1])
    for i in range(N):
        M = uf.size(i)
        if dp[i][M] < 0:
            continue
        roop = K // M
        move = K % M
        if move == 0:
            roop -= 1
            move = M
        for j in range(move):
            ans = max(ans, dp[i][M] * roop + dp[i][j + 1])
    return ans

print(solve())

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()))
 
ans = -float('inf')
for s in range(N):
    S = [] 
    i = P[s] - 1
    S.append(C[i])
    while i != s:
        i = P[i] - 1
        S.append(S[-1] + C[i])
 
    if K <= len(S):
        tmp = max(S[:K])
    elif S[-1] <= 0:
        tmp = max(S)
    else:
        
        tmp1 = S[-1] * (K // len(S) - 1)
        tmp1 += max(S)
        
        tmp2 = S[-1] * (K // len(S))
        r = K % len(S)
        if r != 0:
            tmp2 += max(0, max(S[:r]))
        tmp = max(tmp1, tmp2)
 
    ans = max(ans, tmp)
 
print(ans)

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)

Solution (Python):
N, K = map(int, input().split())
P = [int(i) - 1 for i in input().split()]
Q = [int(i) for i in input().split()]
ans = - float('inf')
for i in range(N):
    now = i
    cnt = 0
    span = 0
    while True:
        span += 1
        cnt += Q[now]
        now = P[now]
        if now == i:
            break
    point = 0
    now = i
    for j in range(1, span + 1):
        point += Q[now]
        now = P[now]       
        if j > K:
            break
        value = point + (max(cnt, 0) * ((K - j) // span))
        ans = max(ans, value)
print(ans)

Solution (Python):
class UnionFind():
    n=1
    par=[0]
    rnk=[0]
    def __init__(self,size):
        self.n=size
        self.par=[i for i in range(self.n)]
        self.rnk=[0 for i in range(self.n)]
    def find(self,vertex1):
        if self.par[vertex1]==vertex1:
            return vertex1
        else:
            self.par[vertex1]=self.find(self.par[vertex1])
            return self.par[vertex1]
    def unite(self,vertex1,vertex2):
        vertex1=self.find(vertex1)
        vertex2=self.find(vertex2)
        if vertex1==vertex2:
            return
        if (self.rnk[vertex1]<self.rnk[vertex2]):
            self.par[vertex1]=vertex2
        else:
            self.par[vertex2]=vertex1
            if(self.rnk[vertex1]==self.rnk[vertex2]):
                self.rnk[vertex1]+=1
    def same(self,vetrex1,vertex2):
        return self.find(vetrex1)==self.find(vertex2)

N,K=map(int,input().split())
P=[int(i)-1 for i in input().split()]
C=[int(i) for i in input().split()]
G=UnionFind(N)
for i in range(N):
    G.unite(i,P[i])
D=dict()
for i in range(N):
    if G.find(i) in D:
        D[G.find(i)]+=1
    else:
        D[G.find(i)]=1

dp=[[0 for j in range(N)] for i in range(N+1)]
for j in range(N):
    dp[0][j]=j
for i in range(N):
    for j in range(N):
        dp[i+1][j]=P[dp[i][j]]


score=[[0 for j in range(N)] for i in range(N)]
for i in range(N):
    for j in range(N):
        score[i][j]=score[i-1][j]+C[dp[i+1][j]]
def maxpoint(j,L):
    if L<=N:
        return max([score[i][j] for i in range(L)])
    else:
        roop=D[G.find(j)]
        cyclepoint=score[roop-1][j]
        if cyclepoint<0:
            return maxpoint(j,roop)
        else:
            if L%roop!=0:
                return maxpoint(j,L%roop)+(L//roop)*cyclepoint
            else:
                return maxpoint(j,roop)+(-1+L//roop)*cyclepoint
ans=[maxpoint(j,K) for j in range(N)]
print(max(ans))

Solution (Python):
def main():
    examC()

def examA():
    S = SI()
    S = ">" + S + "<"
    N = len(S)
    A = [0]*N
    i = 0
    while(i<N-1):
        r = i + 1
        if S[i]==">" and S[i+1]=="<":
            A[i] = 0
            l = i-1
            cur = 0
            while(1<=l):
                cur += 1
                A[l] = max(A[l], cur)
                l -= 1
                if S[l+1]=="<":
                    
                    break
            r = i+1
            cur = 0
            while(r<N-1):
                cur += 1
                A[r] = max(A[r], cur)
                r += 1
                if r==N-1:
                    break
                if S[r]==">":
                    break
        
        i = r
    
    A[0] = 0; A[-1] = 0
    ans = sum(A)
    print(ans)
    return

def examB():
    H, W = LI()
    A = [SI()for _ in range(H)]
    C = defaultdict(int)
    for a in A:
        for s in a:
            C[s] += 1
    B = sorted(C.items())
    
    flag_odd = not (H%2==1 and W%2==1)
    upper_2 = (H%2==1) * (W//2) + (W%2==1) * (H//2)
    for s,c in B:
        if c%2==1:
            if flag_odd:
                print("No")
                return
            flag_odd = True
        elif c%4==2:
            upper_2 -= 1
            if upper_2<0:
                print("No")
                return
    print("Yes")
    return

def examC():
    N, K = LI()
    P = LI()
    C = LI()

    if max(C)<0:
        print(max(C))
        return

    loop = [[0,0]for _ in range(N)]

    for i in range(N):
        checked = set()
        now = i
        score = 0
        while(now not in checked):
            checked.add(now)
            now = P[now]-1
            score += C[now]
        n = len(checked)
        for j in checked:
            loop[j] = [n,score]
    
    ans = 0
    for i in range(N):
        n,s = loop[i]
        score = 0
        if s>0:
            score += (K//n - 1) * s
        ans = max(ans,score)
        now = i
        for j in range(n + K%n):
            now = P[now] - 1
            score += C[now]
            ans = max(ans,score)

    print(ans)
    return

def examD():
    ans = 0
    print(ans)
    return

def examE():
    ans = 0
    print(ans)
    return

def examF():
    ans = 0
    print(ans)
    return

def test():
    i = I()
    li = LI()
    lsi = LSI()
    si = LS()
    print(i)
    print(li)
    print(lsi)
    print(si)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,alphabet_convert,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 1<<31
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    main()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""

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 i in range(N):
    visited = set()
    tmp = 0
    for k in range(K):
        if P[i] in visited: break
        tmp += C[P[i]]
        i = P[i]
        visited.add(i)
        ans = max(ans, tmp)
    if tmp < 0: continue
    l = len(visited)
    rem = K-l
    d,m = divmod(rem,l)
    if m==0 and d > 0:
        m = l
        d -= 1
    tmp *= (d+1)
    for k in range(m):
        tmp += C[P[i]]
        i = P[i]
        ans = max(ans, tmp)

print(ans)

Solution (Python):
n,k = map(int, input().split())
pl = [0] + list(map(int, input().split()))
cl = [0] + list(map(int, input().split()))

valsl = []
already = [False]*(n+1)
for i in range(1,n+1):
    if already[i]: continue
    vals = [cl[i]]
    curr_i = i
    already[i] = True
    while True:
        next_i = pl[curr_i]
        if already[next_i]: break
        v = cl[next_i]
        vals.append(v)
        curr_i = next_i
        already[next_i] = True
    valsl.append(vals)



ans = -10**18
for vals in valsl:
    curr_sum = sum(vals)
    vlen = len(vals)
    for i in range(len(vals)):
        new_vals = vals[i:] + vals[0:i]
        if curr_sum <= 0:
            vmax = -10**18
            v = 0
            for j in range(min(k,vlen)):
                v += new_vals[j]
                vmax = max(v,vmax)
            ans = max(vmax, ans)
        else:
            loop = k//vlen-1
            rem = k-loop*vlen
            v = loop*curr_sum
            vmax = v
            for j in range(rem):
                v += new_vals[j%vlen]
                vmax = max(v,vmax)
            ans = max(vmax, ans)

print(ans)

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

ans = -100_000_000_000
for i in range(N):
    n = 0
    socre_sum = 0
    now = i
    while True:
        n += 1
        socre_sum += C[now]
        now = P[now]
        if i == now:
            break
    score = 0
    now = i
    for j in range(1, n+1):
        score += C[now]
        now = P[now]
        if j > K:
            break
        ans = max(ans, score+max(0, socre_sum)*((K-j)//n))
print(ans)