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

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

    ans = -10 ** 9
    for start in range(N):
        
        now = start
        cycle = []
        total = 0
        for _ in [0] * N:  
            now = P[now]
            cycle.append(C[now])
            total += C[now]
            if now == start:
                break
        
        length = len(cycle)
        score = 0
        for move in range(length):
            score += cycle[move]
            
            if move >= K:
                break
            
            res = score
            if total > 0:
                laps = (K - (move + 1)) // length
                res += total * laps
            ans = max(ans, res)

    print(ans)


if __name__ == '__main__':
    main()

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


ps = list(map(int, input().split()))
cs = list(map(int, input().split()))

graphs = []
vGraphs = []
flags = [False]*n
sumDict = dict()
for i in range(len(ps)):
    p = ps[i]
    index = p - 1
    if flags[index]:
        continue

    current = set()
    values = set()
    currentIndex = index
    while True:
        if flags[currentIndex]:
            break

        current.add(currentIndex)
        values.add(cs[currentIndex])
        flags[currentIndex] = True
        nextIndex = ps[currentIndex] - 1
        currentIndex = nextIndex
    graphs.append(current)
    vGraphs.append(values)

answer = -float('inf')
for i in range(n):

    searchI = 0
    loopSum = 0
    nextIndex = i
    loopCount = 0
    while True:
        nextIndex = ps[nextIndex] - 1
        loopSum += cs[nextIndex]
        loopCount += 1
        if nextIndex == i:
            break

    total = loopSum

    currentSum = 0
    count = 0
    ci = i
    while True:
        count += 1
        if count > k:
            break
        loop = (k - count) // loopCount
        multi = max(0, total) * loop

        ci = ps[ci] - 1

        currentV = cs[ci]
        currentSum += currentV

        answer = max(answer, multi + currentSum)
        if ci == i:
            break

print(answer)

Solution (Python):

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

    ans = -10 ** 9
    for start in range(N):
        
        now = start
        cycle = []
        total = 0
        for _ in [0] * N:  
            now = P[now]
            cycle.append(C[now])
            total += C[now]
            if now == start:
                break
        
        length = len(cycle)
        score = 0
        for move in range(length):
            score += cycle[move]
            
            if move >= K:
                break
            
            res = score
            if total > 0:
                laps = (K - (move + 1)) // length
                res += total * laps
            ans = max(ans, res)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
from itertools import accumulate
 
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]
 
check = [False] * n
loops = []
 
for i in range(n):
    if check[i]:
        continue
    check[i] = True
    next = P[i]
    tmp = [i]
    while next != i:
        check[next] = True
        tmp.append(next)
        next = P[next]
    loops.append(tmp)
 
 
ans = 0
 
for loop in loops:
 
    num = len(loop)
    div = k // num
    r = k % num
    if r == 0:
        r = num
        div -= 1
    L = [C[p] for p in loop]
    ans_tmp = 0  
    sumL = sum(L)
    by_loop = max(sumL, 0) * div
    if k>num and sumL <= 0:
      r = num
    L += L[:r]
    ACC = [0] + list(accumulate(L))
 
    for i in range(num):
            for j in range(i+1, i+r+1):
                ans_tmp = max(ans_tmp, ACC[j] - ACC[i] + by_loop)
 
    ans = max(ans, ans_tmp)
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()))

ans = -float('inf')
for i in range(n):
    score = []
    check = [0] * n
    now = i
    cycle = 0
    for _ in range(k):
        go = p[now] - 1
        if check[go] == 1:
            break
        now = go
        if len(score) == 0:
            score.append(c[now])
        else:
            score.append(score[-1] + c[now])
        check[now] = 1
        cycle += 1

    t = k // cycle
    m = k % cycle

    sum_cycle = score[-1]
    if m == 0:
        ans = max(sum_cycle * t, sum_cycle * (t - 1) + max(score), max(score), ans)
    else:
        ans = max(sum_cycle * t + max(score[:m]), sum_cycle * (t - 1) + max(score), max(score), ans)

print(ans)

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

def f(v, K):
    if K == 0:
        return 0
    if max(v) < 0:
        return max(v)

    n = len(v)
    X = [0]
    for i in range(n):
        X.append(X[-1] + v[i])

    ans = -(10 ** 10)
    for i in range(n + 1):
        for j in range(i):
            if i - j > K:
                continue
            ans = max(ans, X[i] - X[j])
    return(ans)

X = [False for _ in range(N)]
ans = -(10 ** 10)

for i in range(N):
    if X[i]:
        continue
    t = i
    v = []
    while X[t] is False:
        X[t] = True
        v.append(C[t])
        t = P[t]

    n = len(v)
    if K > n:
        s = sum(v)
        x = f(v * 2, n)
        if s > 0:
            a = s * (K // n - 1) + max(s + f(v * 2, K % n), x)
        else:
            a = x
    else:
        a = f(v * 2, K)
    ans = max(a, ans)

print(ans)

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


X = [False for _ in range(N)]

V = []
for i in range(N):
    if X[i]:
        continue
    t = i
    v = []
    while X[t] is False:
        X[t] = True
        v.append(C[t])
        t = P[t]
    V.append(tuple(v))

def f(v, K):
    if K == 0:
        return 0
    if max(v) < 0:
        return max(v)
    n = len(v)

    X = [0]
    for i in range(n):
        X.append(X[-1] + v[i])
    ans = -100000000000
    for i in range(n + 1):
        for j in range(i):
            if i - j > K:
                continue
            ans = max(ans, X[i] - X[j])
    return(ans)

ans = -100000000000
for v in V:
    n = len(v)
    if K > n:
        s = sum(v)
        if s > 0:
            x = s * (K // n) + f(v * 2, K % n)
            y = s * (K // n - 1) + f(v * 2, n)
            a = max(x, y)
        else:
            a = f(v * 2, n)
    else:
        a = f(v * 2, K)
    ans = max(a, ans)

print(ans)

Solution (Python):
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**9-1
for i in range(N):
    seen = [-1]*N
    cumsum = [0]*(N+1)
    now = i
    j = 0
    while seen[now] == -1:
        seen[now] = 1
        now = P[now]
        cumsum[j+1] = cumsum[j] + C[now]
        j += 1
    loop_size = j
    if K <= loop_size:
        ans = max([ans] + cumsum[1:K+1])
    else:
        if cumsum[loop_size] > 0:
            loop_n = K//loop_size - 1
            cumsum2 = cumsum[0:loop_size+1] + [x + cumsum[loop_size] for x in cumsum[1:loop_size+1]]
            score = cumsum[loop_size]*loop_n + max(cumsum2[0:loop_size+K%loop_size+1])
            ans = max(ans, score)
        else:
            ans = max([ans] + cumsum[1:loop_size+1])
print(ans)

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


C = [0] * N
for i in range(N):
    P[i] -= 1
    C[i] = _c[P[i]]

m = 31 


vertex = list()
score = list()
vertex.append(P)
score.append(C)
for b in range(1, m+1):
    p_bth = [0] * N
    c_bth = [0] * N
    for i in range(N):
        p_bth[i] = vertex[b-1][vertex[b-1][i]]
        c_bth[i] = score[b-1][i] + score[b-1][vertex[b-1][i]]
    vertex.append(p_bth)
    score.append(c_bth)


MIN = -(1 << 63) 
prv = [[MIN, 0] for _ in range(N)]
nxt = [[MIN, MIN] for _ in range(N)] 
for b in range(m, -1, -1):
    for i in range(N):
        if (K >> b) & 1:
            nxt[vertex[b][i]][0] = max(nxt[vertex[b][i]][0], prv[i][0] + score[b][i])
            nxt[vertex[b][i]][1] = max(nxt[vertex[b][i]][1], prv[i][1] + score[b][i])
            nxt[i][0] = max(nxt[i][0], prv[i][0], prv[i][1])
        else:
            nxt[vertex[b][i]][0] = max(nxt[vertex[b][i]][0], prv[i][0] + score[b][i])
            nxt[i][0] = max(nxt[i][0], prv[i][0])
            nxt[i][1] = max(nxt[i][1], prv[i][1])
    prv, nxt = nxt, prv

ans = max(max(x) for x in prv)
if ans == 0:
    ans = max(C)

print(ans)

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

def circle_grouping(P):
  P_in=[]
  P_group=[]
  for i in range(N):
    if i in P_in:
      pass
    else:
      start=i
      j=P[i]
      ls=[i]
      P_in.append(i)
      while j!=start:
        ls.append(j)
        P_in.append(j)
        j=P[j]
      P_group.append(ls)
  return P_group

def circle_maximum(A,K):
  max_val=max(A)
  for i in range(len(A)):
    val=0
    for k in range(K):
      pos=(i+k)%len(A)
      val+=A[pos]
      max_val=max(max_val,val)
  return max_val

score=max(C)
P_group=circle_grouping(P)
for A in P_group:
  k_rem=K%len(A)
  cycle=K//len(A)
  if cycle>=1:
    k_rem+=len(A)
    cycle-=1
  B=[C[i] for i in A]
  score=max(score,max(0,sum(B))*cycle+circle_maximum(B,k_rem))
print(score)

Solution (Python):
import copy
import math
import time
import statistics
import math
import itertools
import bisect
from decimal import *



def get_int():
    return int(input())



def get_string():
    return input()



def get_int_list():
    return [int(x) for x in input().split()]



def get_string_list():
    return input().split()



def get_int_multi():
    return map(int, input().split())



def get_string_char_list():
    return list(str(input()))




'''
while (idx < n) and ():

    idx += 1
'''


def main():
    start = time.time()

    n, k = get_int_multi()
    p = get_int_list()
    c = get_int_list()

    kaisuu = [-1] * n
    score = [0] * n
    score_max = [0] * n

    for i in range(n):
        wk = 0
        wk2 = 0
        ichi = i
        for ii in range(n):
            ichi = p[ichi] - 1
            wk += c[ichi]
            wk2 = max(wk2, wk)
            if i == ichi:
                kaisuu[i] = ii + 1
                score[i] = wk
                score_max[i] = wk2
                break

    wk = 0
    ans = - 10 ** 20
    for i in range(n):
        ichi = p[i] - 1
        wk = c[ichi]
        wk2 = c[ichi]
        idx = 0
        while idx < k - 1:
            ichi = p[ichi] - 1
            wk += c[ichi]

            wk2 = max(wk2, wk)
            idx += 1

            
            if (k - 1 - idx > kaisuu[ichi] * 2) and kaisuu[ichi] > 0:
                roopsuu = ((k - 1 - idx) // kaisuu[ichi]) - 1
                wk += roopsuu * score[ichi]
                idx += roopsuu * kaisuu[ichi]
                wk2 = max(wk2, max(wk, score_max[ichi]))

        ans = max(ans, wk2)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
N,K=map(int,input().split())
P=[int(a)-1 for a in input().split()]
C=[int(a) for a in input().split()]
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)
    
print(ans)

Solution (Python):

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

    ans = -10 ** 9
    
    for start in range(N):
        
        now = start
        loop = []
        total = 0
        for _ in [0] * N:  
            now = P[now]
            loop.append(C[now])
            total += C[now]
            if now == start:
                break
        
        length = len(loop)
        score = 0
        for i in range(length):
            score += loop[i]
            
            if i >= K:
                break
            
            res = score
            if total > 0:
                laps = (K - (i + 1)) // length
                res += total * laps
            ans = max(ans, res)
    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
import sys
N,K=map(int,input().split())
plist=[0]+list(map(int,input().split()))
clist=[-float("inf")]+list(map(int,input().split()))

if max(clist)<=0:
  print(max(clist))
  sys.exit(0)
  
if K<=N:
  max_answer=0
  for i in range(1,N+1):
    pos=i
    max_score=0
    score=0
    for c in range(K):
      pos=plist[pos]
      score+=clist[pos]
      max_score=max(score,max_score)
      
    
    max_answer=max(max_answer,max_score)
    
  print(max_answer)
  sys.exit(0)
  
max_answer=0
for i in range(1,N+1):  
  pos=i
  cycle_list=[]
  score_list=[]
  for _ in range(N):
    pos=plist[pos]
    cycle_list.append(pos)
    score_list.append(clist[pos])    
    if pos==i:
      break
      
  num_cycle=K//len(cycle_list)
  cycle_score=sum(score_list)
  
  
  score=0
  max_score=0  
  if cycle_score>=0:
    score+=(num_cycle-1)*cycle_score
  K2=K-len(cycle_list)*(num_cycle-1)

  for _ in range(K2):
    pos=plist[pos]
    score+=clist[pos]
    max_score=max(score,max_score)
  
  
  max_answer=max(max_answer,max_score)
  
print(max_answer)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, K = MAP()
P = LIST()
C = LIST()

loop_point = [0]*N
loop_count = [0]*N
searched = [0]*N

for i in range(N):
	if searched[i]:
		continue
	idx = i
	points = 0
	cnt = 0
	while not searched[P[idx]-1]:
		idx = P[idx]-1
		searched[idx] = 1
		cnt += 1
		points += C[idx]
	loop_count[i] = cnt
	loop_point[i] = points

	while not loop_point[P[idx]-1]:
		idx_next = P[idx]-1
		loop_count[idx_next] = loop_count[idx]
		loop_point[idx_next] = loop_point[idx]
		idx = idx_next

ans = -INF
for i in range(N):
	p = 0
	idx = i
	loop = loop_point[i] > 0 and K > loop_count[i]
	for j in range(1, min(K+1, loop_count[i]+1)):
		idx = P[idx] - 1
		p += C[idx]
		if loop:
			final_p = p + loop_point[i]*((K-j)//loop_count[i])
		else:
			final_p = p
		ans = ans if ans > final_p else final_p
print(ans)

Solution (Python):
import sys, bisect, math, itertools, string, queue, copy








def inp(): return int(input())
def inpm(): return map(int,input().split())
def inpl(): return list(map(int, input().split()))
def inpls(): return list(input().split())
def inplm(n): return list(int(input()) for _ in range(n))
def inplL(n): return [list(input()) for _ in range(n)]
def inplT(n): return [tuple(input()) for _ in range(n)]
def inpll(n): return [list(map(int, input().split())) for _ in range(n)]
def inplls(n): return sorted([list(map(int, input().split())) for _ in range(n)])

n,k = inpm()
P = [0] + inpl()
C = [0] + inpl()

ans = 1000000010 * -1
for start in range(1,n+1):
    l = [0] * (n+1)
    l[start] = 1
    now = start
    score = []
    while True:
        l[now] = 1
        score.append(C[P[now]])
        if l[P[now]] == 1:
            break
        now = P[now]
    
    ruiseki = []
    for i in range(len(score)):
        if i == 0:
            ruiseki.append(score[i])
        else:
            ruiseki.append(ruiseki[i-1] + score[i])

    a = ruiseki[-1] 
    b = max(ruiseki) 
    c = k // len(ruiseki) 
    d = k % len(ruiseki) 

    tmp = 0
    if c == 0:
        tmp = max(ruiseki[:d])
    elif c > 0:
        if a <= 0:
            tmp = b
        elif d == 0:
            tmp = a*(c-1) + b
        else:
            tmp = max(a*c + max(ruiseki[:d]),a*(c-1) + b)
    ans = max(ans,tmp)

print(ans)

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

js = [None for _ in range(n)] 

for s in range(n):
    if js[s]:
        continue
    m = s
    tmp = 0
    memo = [[] for _ in range(n)]
    i = 0
    while True:
        m = p[m] - 1
        tmp += c[m]
        memo[m].append((i, tmp))
        if len(memo[m]) > 1:
            js[m] = (memo[m][1][0] - memo[m][0][0], memo[m][1][1] - memo[m][0][1])
        if len(memo[m]) > 2:
            break
        i += 1

ans = -100000000000
for s in range(n):
    m = s
    tmp = 0
    visited = [0] * n
    for i in range(k):
        m = p[m] - 1
        if visited[m]:
            break
        visited[m] = 1
        tmp += c[m]
        if js[m] and js[m][1] > 0:
            ans = max(ans, tmp + js[m][1] * ((k - i - 1) // js[m][0]))
        else:
            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()))
c = [0]*n
for i in range(n):
    p[i] -= 1
    c[i] = _c[p[i]]
m = 31
MIN = - (1 << 63)
vertex = list()
score = list()
vertex.append(p)
score.append(c)
for a in range(1, m+1):
    p_ath = [0] * n
    c_ath = [0] * n
    for i in range(n):
        p_ath[i] = vertex[a-1][vertex[a-1][i]]
        c_ath[i] = score[a-1][i] + score[a-1][vertex[a-1][i]]
    vertex.append(p_ath)
    score.append(c_ath)
    
prv = [[MIN, 0] for _ in range(n)]
nxt = [[MIN, MIN] for _ in range(n)] 
for b in range(m, -1, -1):
    for i in range(n):
        if (k >> b) & 1:
            nxt[vertex[b][i]][0] = max(nxt[vertex[b][i]][0], prv[i][0] + score[b][i])
            nxt[vertex[b][i]][1] = max(nxt[vertex[b][i]][1], prv[i][1] + score[b][i])
            nxt[i][0] = max(nxt[i][0], prv[i][0], prv[i][1])
        else:
            nxt[vertex[b][i]][0] = max(nxt[vertex[b][i]][0], prv[i][0] + score[b][i])
            nxt[i][0] = max(nxt[i][0], prv[i][0])
            nxt[i][1] = max(nxt[i][1], prv[i][1])
    prv, nxt = nxt, prv
ans = max(max(x) for x in prv)
if ans == 0:
    ans = max(c)
print(ans)

Solution (Python):
import sys

readline = sys.stdin.readline
readall = sys.stdin.read
ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))
prn = lambda x: print(*x, sep='\n')

def solve():
    n, k = nm()
    p = nl()
    _c = nl()
    c = [0]*n
    for i in range(n):
        p[i] -= 1
        c[i] = _c[p[i]]
    m = 31
    MIN = - (1 << 63)
    vertex = list()
    score = list()
    vertex.append(p)
    score.append(c)
    for a in range(1, m+1):
        p_ath = [0] * n
        c_ath = [0] * n
        for i in range(n):
            p_ath[i] = vertex[a-1][vertex[a-1][i]]
            c_ath[i] = score[a-1][i] + score[a-1][vertex[a-1][i]]
        vertex.append(p_ath)
        score.append(c_ath)
    
    prv = [[MIN, 0] for _ in range(n)]
    nxt = [[MIN, MIN] for _ in range(n)] 
    for b in range(m, -1, -1):
        for i in range(n):
            if (k >> b) & 1:
                nxt[vertex[b][i]][0] = max(nxt[vertex[b][i]][0], prv[i][0] + score[b][i])
                nxt[vertex[b][i]][1] = max(nxt[vertex[b][i]][1], prv[i][1] + score[b][i])
                nxt[i][0] = max(nxt[i][0], prv[i][0], prv[i][1])
            else:
                nxt[vertex[b][i]][0] = max(nxt[vertex[b][i]][0], prv[i][0] + score[b][i])
                nxt[i][0] = max(nxt[i][0], prv[i][0])
                nxt[i][1] = max(nxt[i][1], prv[i][1])
        prv, nxt = nxt, prv
    ans = max(max(x) for x in prv)
    if ans == 0:
        ans = max(c)
    print(ans)    
    return

solve()

Solution (Python):
import sys
def input(): return sys.stdin.readline().rstrip()
def ii(): return int(input())
def mi(): return map(int, input().split())
def li(): return list(mi())


def main():
    n, k = mi()
    p = list(map(lambda x: int(x)-1, input().split()))
    c = li()
    ans = -10**18
    for i in range(n):
        v = i
        cycle_cnt = 0
        cycle_sum = 0
        while True:
            cycle_cnt += 1
            cycle_sum += c[v]
            v = p[v]
            if v == i:
                break
        
        cnt = 0
        tmp = 0
        while True:
            tmp += c[v]
            cnt += 1
            if cnt > k:
                break
            r = (k-cnt)//cycle_cnt
            score = tmp+r*max(0, cycle_sum)
            ans = max(ans, score)
            v = p[v]
            if v == i:
                break
    print(ans)



if __name__ == '__main__':
    main()

Solution (Python):
(n,k),p,c=[[*map(int,t.split())]for t in open(0)]
a=-9e9
for i in range(n):
 s=f=0;x,j,*l=i,k
 while~f:x=p[x]-1;s+=c[x];l+=s,;f-=x==i
 for t in l[:k]:j-=1;a=max(a,t+j//len(l)*s*(s>0))
print(a)

Solution (Python):
(n,k),p,c=[[*map(int,t.split())]for t in open(0)]
a=-9e9
for i in range(n):
 s=f=j=0;x,*l=i,
 while~f:x=p[x]-1;s+=c[x];l+=s,;f-=x==i
 for t in l[:k]:j-=1;a=max(a,t+(j+k)//len(l)*s*(s>0))
print(a)

Solution (Python):
(n,k),p,c=[[*map(int,t.split())]for t in open(0)]
a=-9e9
for i in range(n):
 s=f=m=0;x,*l=i,
 while~f:x=p[x]-1;s+=c[x];l+=s,;m+=1;f-=x==i
 for j in range(min(m,k)):a=max(a,l[j]+(~j+k)//m*s*(s>0))
print(a)

Solution (Python):
(n,k),p,c=[[*map(int,t.split())]for t in open(0)]
a=-9e9
for i in range(n):
 s=t=f=m=0;x,*l=i,
 while~f:x=p[x]-1;l+=c[x],;s+=c[x];m+=1;f-=x==i
 for j in range(min(m,k)):t+=l[j];a=max(a,t+(~j+k)//m*s*(s>0))
print(a)

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees, log2, gcd
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left, insort, insort_left
from heapq import heappush, heappop
from functools import reduce, lru_cache
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def TUPLE(): return tuple(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7 

from decimal import *



N, K = MAP()
P = LIST()
C = LIST()

check = [0]*N 
score = []

for i in range(N):
	if check[i]:
		continue

	tmp = []
	while check[i] == 0:
		check[i] = 1
		i = P[i]-1
		tmp.append(C[i])
	score.append(tmp)

ans = -INF
for x in score:
	x_acc = list(accumulate([0] + x + x))
	n = len(x)
	tmp_max = -INF

	for i, j in combinations(range(2*n+1), 2):
		if j-i <= min(K, n):
			if tmp_max < x_acc[j]-x_acc[i]:
				tmp_max = x_acc[j]-x_acc[i]
				cnt = j-i
	tmp_ans = -INF

	if 0 >= x_acc[n]:
		tmp_ans = tmp_max

	else:
		if cnt <= K%n:
			tmp_ans = x_acc[n]*(K//n) + tmp_max
		else:
			tmp_max2 = 0
			for i, j in combinations(range(2*n+1), 2):
				if j-i <= K%n:
					if tmp_max2 < x_acc[j]-x_acc[i]:
						tmp_max2 = x_acc[j]-x_acc[i]
			tmp_ans = max(x_acc[n]*(K//n-1)+tmp_max, x_acc[n]*(K//n) + tmp_max2)

	ans = max(ans, tmp_ans)

print(ans)

Solution (Python):
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    N, K = LI()
    P = LI_()
    C = LI()
    G = [-1 for _ in range(N)]
    for i, p in enumerate(P):
        G[i] = p
    seen = set()

    loop_score = []
    loop_size = []
    loop_id2node = collections.defaultdict(list)

    _id = 0
    def calc_one_loop(v):
        nodes = set()
        if G[v] == -1:
            return -1, -1
        
        score = 0
        size = 0
        while G[v] not in seen:
            v = G[v]
            seen.add(v)
            nodes.add(v)
            score += C[v]
            size += 1
        return score, size, nodes

    for i in range(N):
        if i in seen:
            continue
        score, size, nodes = calc_one_loop(i)
        if score == -1 and size == -1:
            continue
        loop_score.append(score)
        loop_size.append(size)
        loop_id2node[_id].extend(list(nodes))
        seen.add(i)
        _id += 1

    
    
    ans = -inf
    for i in range(_id):
        
        n_loop = K // loop_size[i]

        
        score_after = [[0] for _ in range(N)]
        for v in loop_id2node[i]:
            max_move_cnt = loop_size[i] + 1
            move_cnt = 0
            cum_score = 0
            cur_v = v
            while move_cnt < max_move_cnt:
                cur_v = G[cur_v]
                cum_score += C[cur_v]
                score_after[v].append(cum_score)
                move_cnt += 1
        
        if loop_score[i] <= 0:
            max_step = min(K, loop_size[i])
            score = 0
        else:
            
            
            score = 0
            max_step = loop_size[i]

            
            
            
            
            
            
            

        
        for l in range(1, max_step + 1):
            for v in loop_id2node[i]:
                cp_score = score
                cnt = 0
                cp_score += score_after[v][l]
                
                if l > K:
                    continue
                
                if K - l >= loop_size[i]:
                    cp_score = max(cp_score, cp_score + loop_score[i] * ((K - l) // loop_size[i]))
                ans = max(ans, cp_score)
    print(ans)

main()

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

ans = -1e18
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
        if ans < now:
            ans = now
print(ans)

Solution (Python):
import sys
import itertools

import time
import math
import heapq
from collections import defaultdict
sys.setrecursionlimit(10 ** 7)
 
INF = 10 ** 9 + 7
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines



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


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