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()))
ans = c[0]
jud = []
for i in range(n):
    if i not in jud:
        l = []
        j = p[i] - 1
        while j not in jud:
            jud.append(j)
            l.append(c[p[j]-1])
            j = p[j] - 1
        le = len(l)
        su = sum(l)
        l *= 2
        if su > 0:
            v = (k//le)*su
            ans = max(ans, v)
        for ii in range(le):
            val = 0
            for cnt in range(0, le):
                val += l[ii + cnt]
                if su > 0:
                    v = val + ((k - cnt - 1)//le)*su
                    ans = max(ans, v)
                else:
                    ans = max(ans, val)

print(ans)

Solution (Python):
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

n, k = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))

from collections import deque

def bfs(queue, cycle_index, cycle_num):
    cycle = []
    score = 0
    while queue:
        current = queue.popleft()
        cycle_index[current] = cycle_num
        cycle.append(current)
        score += c[current]

        if p[current] not in cycle_index:
            queue.append(p[current])
    return cycle, score

cycle_index = {}
cycle_num = 0
cycles = []
for i in range(1, n + 1):
    if i in cycle_index:
        continue
    queue = deque([i])
    cycle, score = bfs(queue, cycle_index, cycle_num)
    cycles.append((cycle, score))
    cycle_num += 1

ans = None
for i in range(1, n + 1):
    cycle, score = cycles[cycle_index[i]]
    tmp_ans = 0

    cum = [0]
    current = i
    for j in range(1, len(cycle)):
        current = p[current]
        cum.append(cum[-1] + c[current])

    if score > 0:
        q = (k // len(cycle))
        r = k % len(cycle)
        
        
        if r == 0:
            tmp_ans = max((score * q), (score * (q - 1)) + max(cum[1:]))
        else:
            tmp_ans = (score * q) + max(cum[1:r+1])
    else:
        r = min(k, len(cycle))
        tmp_ans = max(cum[1:r+1])

    if ans is None:
        ans = tmp_ans
    else:
        ans = max(ans, tmp_ans)
print(ans)

Solution (Python):
import sys
from itertools import islice, repeat


def _resolve(costs, k):
    sum_ = sum(costs)
    v = 0
    if k >= len(costs):
        if sum_ > 0:
            x = k // len(costs) - 1
            v = x * sum_
            k -= x * len(costs)
        else:
            k = len(costs)

    points = [v] * (len(costs) * (k + 1))
    for i in range(k):
        for n in range(len(costs)):
            points[(i + 1) * len(costs) + n] = points[i * len(costs) + n] + costs[(i + n) % len(costs)]
    
    ans = max(points)
    if ans == 0:
        y = max(costs)
        if y < 0:
            ans = y
    return ans


def resolve(in_):
    N, K = map(int, next(in_).split())
    P = [0] + list(map(int, next(in_).split()))
    C = [0] + list(map(int, next(in_).split()))

    graphs = []
    used = [False] * len(P)
    for index in range(1, len(P)):
        if used[index]:
            continue
        used[index] = True
        graph = [C[index]]
        index = P[index]
        while not used[index]:
            graph.append(C[index])
            used[index] = True
            index = P[index]
        graphs.append(graph)

    ans = max(map(_resolve, graphs, repeat(K)))
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

Solution (Python):
N, K = map(int, input().split())
P, C = [list(map(int, input().split())) for _ in range(2)]
c = [1] * N
m = [[0] * (N+1) for i in range(N)]
for i in range(N):
    m[i][1] = (C[P[i]-1])
ans = max(C)
for i in range(N):
    j = i
    while P[j]-1 != i:
        j = P[j]-1
        c[i] += 1
        m[i][c[i]] = m[i][c[i]-1] + C[P[j]-1]
    if m[i][c[i]] > 0:
        ans = max(ans, m[i][c[i]] * (K//c[i]-1) + max(m[i] + [m[i][c[i]] + m[i][j+1] for j in range(K%c[i])]))
    else:
        ans = max(ans, max(m[i][1:min(c[i],K)+1]))
print(ans)

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

    used = [0]*N
    ans = -float('inf')
    for x in range(N):
        if used[x]:
            continue
        used[x] = 1
        Q = [C[x]]

        while not used[P[x]]:
            x = P[x]
            used[x] = 1
            Q.append(C[x])

        ret = check(Q, K)
        if ret > ans:
            ans = ret

    print(ans)


def check(Q, K):
    length = len(Q)
    tot = sum(Q)
    Q *= 2
    ret = -float('inf')
    for i in range(length):
        accum = 0
        for k in range(1, min(K, length)+1):
            accum += Q[i+k]
            if tot > 0:
                ret = max(ret, accum + tot * ((K-k)//length))
            else:
                ret = max(ret, accum)
    return ret


if __name__ == '__main__':
    main()

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

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

INF = float('inf')

max_points = []
for i in range(N):
    max_point = -INF
    visit = [0] * N
    visit[i] = 1
    S = [0]
    pos = P[i]
    loop = 0  
    while True:
        if visit[pos] == 0:
            visit[pos] = 1
            S.append(S[loop] + C[pos])
            pos = P[pos]
            loop += 1
        else:
            S.append(S[loop] + C[pos])
            pos = P[pos]
            loop += 1
            break

    loop_point = S[loop]
    
    
    if loop > K:
        max_point = max(S[1:K+1])
    else:
        if loop_point > 0:
            loop_num = K // loop
            max_point = max(max_point, loop_point * loop_num + max(S[:(K%loop)+1]))
            max_point = max(max_point, loop_point * (loop_num-1) + max(S[1:loop]))
        else:
            max_point = max(S[1:loop+1])

    max_points.append(max_point)

print(max(max_points))

Solution (Python):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
INF = 10**9+1

def solve():
    ans = -INF

    for i in range(N):
        memo = [0] * (N+1)
        j = 0
        p = i
        while j < N:
            memo[j+1] = memo[j] + C[p]
            p = P[p] - 1
            j += 1
            if p == i:
                break
        tans =-INF
        if memo[j] > 0:
            for k in range(j):
                q = (K-k-1) // j
                tans = max(tans, memo[k+1] + memo[j] * q)
        else:
            for k in range(min(K, j)):
                tans = max(tans, memo[k+1])

        ans = max(ans, tans)
    return ans

if __name__ == "__main__":
    print(solve())

Solution (Python):
import sys
from itertools import islice, repeat


def _resolve(costs, k):
    sum_ = sum(costs)
    v = 0
    if k >= len(costs):
        if sum_ > 0:
            x = k // len(costs) - 1
            v = x * sum_
            k -= x * len(costs)
        else:
            k = len(costs)

    points = [v] * (len(costs) * (k + 1))
    for i in range(k):
        for n in range(len(costs)):
            points[(i + 1) * len(costs) + n] = points[i * len(costs) + n] + costs[(i + n) % len(costs)]
    
    ans = max(points)
    if ans == 0:
        y = max(costs)
        if y < 0:
            ans = y
    return ans


def resolve(in_):
    N, K = map(int, next(in_).split())
    P = [0] + list(map(int, next(in_).split()))
    C = [0] + list(map(int, next(in_).split()))

    graphs = []
    p = set(P[1:])
    while p:
        index = p.pop()
        graph = [C[index]]
        index = P[index]
        while index in p:
            graph.append(C[index])
            p.remove(index)
            index = P[index]
        graphs.append(graph)

    ans = max(map(_resolve, graphs, repeat(K)))
    return ans


def main():
    answer = resolve(sys.stdin.buffer)
    print(answer)


if __name__ == '__main__':
    main()

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 = list(map(int, input().split()))
p = list(map(lambda x: int(x) - 1, input().split()))
c = list(map(int, input().split()))

best = max(c)
for i in range(n):
    curr = 0
    score = [0]
    start = i
    while p[start] != i:
        start = p[start]
        curr += c[start]
        score.append(curr)
    cycle_score = score[-1] + c[i]
    cycle_len = len(score)

    for j in range(cycle_len):
        if j <= k and j != 0:
            
            cycles = (k-j)//cycle_len
            thing = score[j] + max(0, cycle_score) * cycles
            best = max(best, thing)
        elif j == 0 and k >= cycle_len:
            thing = cycle_score * k//cycle_len
            best = max(best, thing)
print(best)

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 = []

    S.append(C[s])
    i = P[s] - 1

    while i != s:
        S.append(S[-1] + C[i])
        i = P[i] - 1
    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()))
P = [p-1 for p in P]





visited = set() 

ans = 0
for i in range(N):
  if i in visited: 
    continue
  
  
  j = i
  C_tmp = [] 
  while j not in visited:
    C_tmp.append(C[j])
    visited.add(j)
    j = P[j] 
    
  
  N_tmp = len(C_tmp) 
  tmp = 0 
  
  
  
  
  loop_sum = max(0, sum(C_tmp)) 
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  
  base = loop_sum * (K // N_tmp)
  
  
  
  ans = max(ans, base) 
  behind = False 
  for l in range(1,min(N_tmp, K+1)): 
    if (not behind) and l > K % N_tmp: 
      behind = True
      base -= loop_sum
    summ = sum(C_tmp[0:l]) + base
    for j in range(N_tmp):
      ans = max(ans, summ) 
      summ += C_tmp[(j+l)%N_tmp] - C_tmp[j] 
      
      


print(max(C) if max(C) < 0 else ans)

Solution (Python):
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
from collections import deque
toku=[0]*(n+1)
for i in range(1,n+1):
  ans=[0]
  d=deque()
  visit=[0]*(n+1)
  d.append(i)
  while d:
    now=d.pop()
    if visit[now]==0:
      visit[now]=1
      ans.append(ans[-1]+c[p[now-1]-1])
      d.append(p[now-1])
  syuki=sum(visit)
  if ans[-1]>=0:
    if k%syuki==0:
      toku[i]=max((k//syuki)*ans[-1],(k//syuki-1)*ans[-1]+max(ans))
      
    else:
      toku[i]=(k//syuki)*ans[-1]+max(ans[1:k%syuki+1])
  else:
    if k//syuki==0:
      toku[i]=max(ans[1:k%syuki+1])
    else:
      toku[i]=max(ans[1:])
print(max(toku[1:]))

Solution (Python):
import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, gcd
from itertools import accumulate, permutations, combinations, product, groupby, combinations_with_replacement
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from heapq import heappush, heappop
from functools import reduce
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 ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

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):
def f(x):
  D=[-1]*(N+1)
  D[x]=0
  S=[None]*(N+1)
  S[x]=0
  ima=x+0
  for count in range(1, K+1):
    if D[P[ima]]<0:
      D[P[ima]]=count
      S[P[ima]]=S[ima]+C[P[ima]]
      ima=P[ima]+0
    else:
      if S[ima]+C[P[ima]]>S[P[ima]]:
        isshu=count-D[P[ima]]
        atonanshu=max((K-count)//isshu-1, 0)
        atonanho=K-(count+isshu*atonanshu)
        agatta=S[ima]+C[P[ima]]-S[P[ima]]
        S[P[ima]]=S[ima]+C[P[ima]]+agatta*atonanshu
        D[P[ima]]=D[ima]+1
        
        ima=P[ima]+0
        for _ in range(atonanho):
          S[P[ima]]=S[ima]+C[P[ima]]
          D[P[ima]]=D[ima]+1
          ima=P[ima]+0
      break
      
  if D[x]==0:
    S[x]=None
  return max([s for s in S if s is not None])

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

print(max([f(x) for x in range(1, N+1)]))

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 = max(c)
for i in range(n):
    curr = 0
    score = [0]
    posi = i
    while p[posi] != i:
        posi = p[posi]
        curr += c[posi]
        score.append(curr)
    cycle_score = score[-1] + c[i]
    cycle_len = len(score)
    
    for j in range(cycle_len):
        if j <= k and j != 0:
            cycles = (k - j)//cycle_len
            thing = score[j] + max(0, cycle_score) * cycles
            ans = max(ans, thing)
        
        elif j == 0 and k >= cycle_len:
            thing = cycle_score * k // cycle_len
            ans = max(ans,thing)

print(ans)

Solution (Python):
import bisect
import sys,io
import math
from collections import deque
from heapq import heappush, heappop

def sRaw():
    return input().rstrip("\r")


def iRaw():
    return int(input())


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


def isRaw():
    return list(map(int, ssRaw()))


INF = 1 << 29

DIV = (10**9) + 7


def mod_inv_prime(a, mod=DIV):
    return pow(a, mod-2, mod)


def mod_inv(a, b):
    r = a
    w = b
    u = 1
    v = 0
    while w != 0:
        t = r//w
        r -= t*w
        r, w = w, r
        u -= t*v
        u, v = v, u
    return (u % b+b) % b


def CONV_TBL(max, mod=DIV):
    fac, finv, inv = [0]*max, [0]*max, [0]*max
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, max):
        fac[i] = fac[i-1]*i % mod
        inv[i] = mod - inv[mod % i] * (mod//i) % mod
        finv[i] = finv[i-1]*inv[i] % mod

    class CONV:
        def __init__(self):
            self.fac = fac
            self.finv = finv
            pass

        def ncr(self, n, k):
            if(n < k):
                return 0
            if(n < 0 or k < 0):
                return 0
            return fac[n]*(finv[k]*finv[n-k] % DIV) % DIV

    return CONV()


def cumsum(As):
    s = 0
    for a in As:
        s += a
        yield s


sys.setrecursionlimit(200005)


def dijkstra(G,start=0):
    heap = []
    cost = [INF]*len(G)
    heappush(heap,(0,start))
    while len(heap)!=0:
        c,n = heappop(heap)
        if cost[n] !=INF:
            continue
        cost[n]=c
        for e in G[n]:
            ec,v = e
            if cost[v]!=INF:
                continue
            heappush(heap,(ec+c,v))
    return cost


def main():

    N,K = isRaw()
    Ps = isRaw()
    Cs = isRaw()
    ans = max(Cs)
    for n in range(N):
        curPos = n
        cycles =[]
        visited = {}
        lastCost = 0
        vidx = 0
        loopStart = -1
        while True:
            visited[curPos] = vidx
            lastCost = lastCost+Cs[curPos]
            cycles.append(lastCost)
            curPos= Ps[curPos]-1
            
            if curPos in visited:
                loopStart = visited[curPos]
                break
        
        c_len = len(cycles)
        c_score = cycles[-1]
        if K>=c_len:
            ans = max(ans,c_score*(K//c_len))
        for c in range(0,min(c_len,K)):
            n_cycle = (K-c-1)//c_len
            score = cycles[c]+max(0,c_score*n_cycle)
            ans = max(score,ans)
    print (ans)

         
main()

Solution (Python):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
INF = 10**9+1

def solve():
    cycles = []
    memo = [False] * N
    i = 0
    while i < N-1:
        cycle = []
        j = i
        while not memo[j]:
            cycle.append(j)
            memo[j] = True
            j = P[j] - 1
        k = i
        for i in range(k, N):
            if not memo[i]:
                break
        cycles.append(cycle)

    ans = -INF

    for cycle in cycles:
        n = len(cycle)
        
        
        memo = [-INF] * n
        for i in range(n):
            s = 0
            for j in range(n):
                s += C[cycle[(i+j)%n]]
                memo[j] = max(memo[j], s)
        tmpmax = -INF
        imax = -1
        if K < n:
            for i in range(K):
                if tmpmax < memo[i]:
                    tmpmax = memo[i]
                    imax = i+1
        else:
            if memo[-1] > 0:
                for i in range(n):
                    q = (K-i-1) // n
                    tmpmax = max(tmpmax, memo[i] + memo[-1] * q)
            else:
                for i in range(n):
                    tmpmax = max(tmpmax, memo[i])

        ans = max(ans, tmpmax)
    return ans

if __name__ == "__main__":
    print(solve())

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):
    done = set()
    S = []

    done.add(i)
    S.append(C[i])
    i = P[i] - 1
    while i not in done:
        done.add(i)
        S.append(S[-1] + C[i])
        i = P[i] - 1
    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()))
P = [p - 1 for p in P]
C = list(map(int, input().split()))

vis = [False] * N
ans = [-float('inf')] * N

for root in range(N):
    if vis[root]:
        continue

    cycle = [root]
    costs = [C[root]]
    u = P[root]
    while u != root:
        cycle.append(u)
        costs.append(C[u])
        u = P[u]
    
    for u in cycle:
        vis[u] = True

    L = len(cycle)
    S = sum(costs)
    for i, v in enumerate(cycle):
        
        
        
        
        

        
        
        
        

        if S > 0:
            rem_cost = 0
            for rem in range(1, min(L, K) + 1):
                rem_cost += costs[(i + rem) % L]
                t = (K - rem) // L
                ans[v] = max(ans[v], rem_cost + t * S)
        else:
            rem_cost = 0
            for rem in range(1, min(L, K) + 1):
                rem_cost += costs[(i + rem) % L]
                ans[v] = max(ans[v], rem_cost)

print(max(ans))

Solution (Python):


N, K = map(int, input().split())
P_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))

checked_list = [0 for _ in range(N)]
min_INF = -1 * 10 ** 10
max_score = min_INF
for i in range(N):
    if checked_list[i] == 1:
        continue
    posit = i
    loop_list = [posit]
    score_list = []
    for j in range(N):
        posit = P_list[posit] - 1
        if j == 0:
            score_list.append(C_list[posit])
        else:
            score_list.append(score_list[-1] + C_list[posit])
        if posit in loop_list:
            break
        loop_list.append(posit)

    len_loop = len(loop_list)
    max_score_list = max(score_list)
    around_score = score_list[-1]
    temp_score_base = 0
    if around_score > 0 and K // len_loop > 0:
        temp_score_base += (K // len_loop - 1) * around_score
    for k in range(len_loop):
        
        
        checked_list[loop_list[k]] = 1
        temp_max_score = temp_score_base
        rest_score = min_INF
        if around_score > 0 and K // len_loop > 0:
            
            rest_score = max(max_score_list, max(score_list[:K % len_loop], default=min_INF) + around_score)
            
        rest_score = max(max(score_list[:min(K, len_loop)]), rest_score)
        temp_max_score = temp_max_score + rest_score
        
        max_score = max(max_score, temp_max_score)
        
        now_score = score_list.pop(0)
        len_score = len(score_list)
        score_list = [score_list[l] - now_score for l in range(len_score)]
        score_list.append(score_list[-1] + now_score)

print(max_score)

Solution (Python):
import sys

sys.setrecursionlimit(50000)
N,K= [int(v) for v in input().split()]
P = [int(v) - 1 for v in input().split()]
C = [int(v) for v in input().split()]

visited = [True for _ in range(N)]
cycle = []


ans = -float('inf')
for sn in range (N):
    cost = []
    nn = sn
    while True:
        cost.append(C[nn])
        nn = P[nn]
        if sn == nn:
            break
    total = sum(cost)
    l = len(cost)

    t = 0
    for i in range(l):
        t += cost[i]
        if i+1 > K: break
        now = t
        if total > 0:
            e = (K-i-1)//l
            now += total * e
        ans = max(ans,now)


print(int(ans))

Solution (Python):
import sys
from numpy import*
def main(n,k,p,c):
    m=-10**12
    for i in range(n):
        s=i
        t=1
        x=c[s]
        while p[s]-1!=i:
            s=p[s]-1
            t+=1
            x+=c[s]
        if x>0:
            a=(k//t-1)*x
            if a>m:m=a
            s=i
            for _ in range(k%t+t):
                s=p[s]-1
                a+=c[s]
                if a>m:m=a
        else:
            a=0
            s=i
            for _ in range(min(k,t)):
                s=p[s]-1
                a+=c[s]
                if a>m:m=a
    return m
if sys.argv[-1]=='ONLINE_JUDGE':
  from numba.pycc import CC
  cc=CC('my_module')
  cc.export('main','i8(i8,i8,i8[:],i8[:])')(main)
  cc.compile()
  exit()
from my_module import main
(n,k),p,c=[int_(t.split())for t in open(0)]
print(main(n,k,p,c))

Solution (Python):
(n,k),p,c  = [list(map(int, s.split())) for s in open(0)]

pset = set(p)
ans = c[0]
for x in range(1,n+1):
    _sum = [0 for _ in range(2*n)]
    num = 0
    while x in pset:
        pset.remove(x)
        _sum[num + 1] = _sum[num] + c[x-1]
        x = p[x-1]
        num += 1
    if num > 0:
        for i in range(1,num):
            _sum[num + i] += _sum[num] + _sum[i]
        
        if k//num > 0:
            tmp = _sum[num] * (k//num)
            if tmp > ans:
                ans = tmp
        for i in range(1, min(k+1,num)):
            base = max(0, _sum[num]) * ((k-i)//num)
            for j in range(num):
                tmp = _sum[j+i] - _sum[j] + base
                if tmp > ans:
                    ans = tmp
print(ans)

Solution (Python):
from itertools import accumulate

def main():
    inf=float("inf")
    n,k=map(int,input().split())
    plst=list(map(int,input().split()))
    clst=list(map(int,input().split()))
    sm=-inf

    seen=[0]*n
    for i in range(n):
        if seen[i] : continue
        pos=i
        work=[]
        while not seen[pos]:
            seen[pos]=1
            work.append(clst[pos])
            pos=plst[pos]-1
        nwork=len(work)
        loop_sum=sum(work)
        work=[0]+list(accumulate(work))
        
        numcut=min(nwork,k)

        for i in range(nwork):
            for j in range(i,i+numcut):
                if j<nwork :
                    smwork=work[j+1]-work[i]
                else :
                    smwork=work[nwork]-work[i]+work[j-nwork+1]
                if loop_sum>0:
                    smwork+=loop_sum*((k-(j+1-i))//nwork) 
                if smwork>sm : sm=smwork

    print(sm)

main()

Solution (Python):

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


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

ans = -12345678901234567


for st in range(n):
    score = 0
    now = st

    
    for i in range(1,k+1):
        now = p[now]
        score += c[now]
        ans = max(ans,score)

        
        if now == st:
            
            
            
            cnt = k//i - 1
            if cnt > 1:
                score *= cnt
                i *= cnt
                ans = max(ans,score)
            break

    
    for j in range(i+1,k+1):
        now = p[now]
        score += c[now]
        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()))

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

ans = -12345678901234567
for st in range(n):
    score = 0
    now = st

    
    for i in range(1,k+1):
        now = p[now]
        score += c[now]
        ans = max(ans,score)
        if now == st:
            cnt = k//i - 1
            if cnt > 1:
                score *= cnt
                i *= cnt
                ans = max(ans,score)
            break

    for j in range(i+1,k+1):
        now = p[now]
        score += c[now]
        ans = max(ans,score)
print(ans)

Solution (Python):


import sys


def main():
    
    inf = 2 ** 63 - 1             
    sys.setrecursionlimit(10**6)    
    def input():  return sys.stdin.readline().rstrip()
    def ii():     return int(input())
    def isp():    return input().split()
    def mi():     return map(int, input().split())
    def mi_0():   return map(lambda x: int(x)-1, input().split())
    def lmi():    return list(map(int, input().split()))
    def lmi_0():  return list(map(lambda x: int(x)-1, input().split()))
    def li():     return list(input())
    def debug(x): print(x, file=sys.stderr)



    def calc_score(start):
        order = [None] * n
        accum = [None] * n
        order[start] = 0
        accum[start] = 0
        place = start
        cnt = 0
        current_score = 0
        M = -inf

        while cnt < k:
            place = P[place]    
            cnt += 1    
            current_score += C[place]    
            M = max(M, current_score)    
            if order[place] is None:
                
                order[place] = cnt
                accum[place] = current_score
            else:
                
                head_len = order[place]
                loop_len = cnt - head_len
                head_score = accum[place]
                loop_gain = current_score - accum[place]
                if loop_gain <= 0:
                    
                    return M
                else:
                    
                    loop_times, res = divmod(k - head_len, loop_len)
                    
                    res_score = 0    
                    tmp_score = 0    
                    tmp_place = place    
                    for _ in range(res):
                        tmp_place = P[tmp_place]
                        tmp_score += C[tmp_place]    
                        res_score = max(res_score, tmp_score)
                    
                    loop_score = head_score + loop_times * loop_gain + res_score
                    stop_score = M + (loop_times - 1) * loop_gain
                    return max(loop_score, stop_score)

        
        return M
            

    n, k = mi()
    P = lmi_0()
    C = lmi()

    ans = -inf
    for i in range(n):
        score = calc_score(i)
        
        ans = max(ans, score)
    print(ans)


if __name__ == "__main__":
    main()