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()))
r = -10**9
for i in range(n):
  ans=c[i]
  e =[ans]
  f = i
  a = 1
  while a<k:
    i = p[i]-1
    if i == f:
      break
    a+=1
    ans+=c[i]
    e.append(ans)
  if e[-1]>0 and a<k:
    w = k%len(e)
    if w!=0:
      y = k//len(e)*e[-1]+max(e[:w])
    else:
      y =( k//len(e)-1)*e[-1]+max(e)
    g=y
  else:
    g=max(e)
  r = max(r,g)
print(r)

Solution (Python):
import sys

def main():
    input = sys.stdin.readline
    n, k = map(int, input().split())
    p = list(map(lambda x:int(x) - 1, input().split()))
    c = list(map(int, input().split()))
    seen = [0] * n
    accumulate = []
    for i in range(n):
        if seen[i] == 0:
            accumulate.append([c[i]])
            pre = i
            while True:
                if seen[pre] == 1:
                    accumulate[-1].pop()
                    break
                seen[pre] = 1
                now = p[pre]
                pre = now
                accumulate[-1].append(accumulate[-1][-1] + c[now])
    
    ans = -float("INF")
    for lst in accumulate:
        if len(lst) >= k:
            for interval in range(1, k + 1):
                for start in range(len(lst)):
                    if start + interval >= len(lst):
                        num = lst[-1] + lst[(start + interval) % len(lst)] - lst[start]                    
                    else:
                        num = lst[(start + interval)] - lst[start]
                    ans = max(ans, num)
        else:
            if lst[-1] > 0:
                for interval in range(1, len(lst) + 1):
                    for start in range(len(lst)):
                        num = (k - interval) // len(lst) * lst[-1]
                        if start + interval >= len(lst):
                            num += (lst[-1] + lst[(start + interval) % len(lst)] - lst[start])                    
                        else:
                            num += (lst[(start + interval)] - lst[start])
                        ans = max(ans, num)
                """
                for interval in range(1, k - len(lst) * (k // len(lst)) + 1):
                    for start in range(len(lst)):
                        num = (k // len(lst)) * lst[-1]
                        if start + interval >= len(lst):
                            num += (lst[-1] + lst[(start + interval) % len(lst)] - lst[start])
                        else:
                            num += lst[(start + interval)] - lst[start]
                        ans = max(ans, num)
                """
            else:
                for interval in range(1, len(lst)):
                    for start in range(len(lst)):
                        if start + interval >= len(lst):
                            num = lst[-1] + lst[(start + interval) % len(lst)] - lst[start]                    
                        else:
                            num = lst[(start + interval)] - lst[start]
                        ans = max(ans, num)
            
    print(ans)
if __name__ == '__main__':
    main()

Solution (Python):
n, limit = list(map(int, input().split()))
permute = list(map(int, input().split()))
score = list(map(int, input().split()))

visited = [False] * n

ans = -10 ** 16

for i in range(n):
    if visited[i]:
        continue

    score_circle = []
    now = i
    while True:
        visited[now] = True
        score_circle.append(score[now])

        next_ = permute[now] - 1
        if visited[next_]:
            
            break
        now = next_
    
    period = len(score_circle)

    score_circle *= 2
    
    cumsum = [0] * (2 * period + 1)
    for j in range(1, 2*period+1):
        cumsum[j] = cumsum[j-1] + score_circle[j-1]
    
    p_sum_max = [-(10**15)] * (period + 1)
    for k in range(period):
        for ll in range(period):
            p_sum_max[ll] = max(p_sum_max[ll], cumsum[k+ll] - cumsum[k])
    
    ans = max([ans] + p_sum_max[1:min(period+1, limit+1)])

    q, resi = divmod(limit, period)

    if q >= 1:
        ans = max(ans, cumsum[period] * (q-1) + max(p_sum_max[1:]))
        ans = max(ans, cumsum[period] * (q) + max(p_sum_max[:resi + 1]))

        

print(ans)

Solution (Python):
import math

N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
loopid = [-1 for _ in range(N)]
loop_found = 0
for i in range(N):
    if loopid[i] != -1:
        continue
    loopid[i] = loop_found
    j = P[i]-1
    while loopid[j] == -1:
        loopid[j] = loop_found
        j = P[j]-1
    loop_found += 1

loops = [[] for _ in range(loop_found)]
for nodeid, id in enumerate(loopid):
    loops[id].append(nodeid)

ans = -math.inf
for loop in loops:
    K_tmp = K
    score_tmp = 0
    cs = []
    j = loop[0]
    for _ in range(len(loop)):
        cs.append(C[j])
        j = P[j] - 1
    if sum(cs) >= 0:
        score_tmp += sum(cs)*max(0, K//len(loop)-1)
    K_tmp %= len(loop)
    if K>=len(loop):
        K_tmp += len(loop)

    max_rest = -math.inf
    cs = cs + cs + cs
    for i in range(1, len(cs)):
        cs[i] += cs[i-1]
    j = -1
    tmp_min = math.inf
    for i, c in enumerate(cs):
        max_rest = max(max_rest, c-tmp_min)
        if tmp_min >= c:
            tmp_min = c
            j = i
        if i-j >= K_tmp:
            tmp_min = cs[j+1]
            j += 1
            x = j
            for k, c_ in enumerate(cs[j+1:i+1]):
                if tmp_min >= c_:
                    tmp_min = c_
                    x = k + j + 1
            j = x
    score_tmp += max_rest
    ans = max(ans, score_tmp)
print(ans)

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


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

ans=-1*(10**10)

if K<10000000:
    for i in range(N):
        tmp=0
        pos=i
        count=0
        while count<K:    
            
            tmp+=C[P[pos]-1]
            if tmp>ans:
                ans=tmp
            
            pos=P[pos]-1
            count+=1
     
    print(ans)
else:
    
    for i in range(N):
        tmp=0
        pos=i
        gpos=i
        count=0
        while count<K:    
            
            tmp+=C[P[pos]-1]
            if tmp>ans:
                ans=tmp
            
            
            pos=P[pos]-1
            count+=1
            if pos==gpos:
                divide=K//count-1
                tmp=tmp*divide
                count=count*divide
                gpos=10**10
            
    
    print(ans)

Solution (Python):
N, K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
scores = []
for i in range(N):
  pos = P[i]-1
  s = [C[i]]
  j = 1
  while j < K and pos != i:
    s.append(s[-1]+C[pos])
    pos = P[pos]-1
    j += 1
  smax = max(s)
  length = len(s)
  if length < K and s[-1] > 0:
    if K%length != 0:
      smod = s[:K%length]
      smodmax = max(smod)
    else:
      smodmax = 0
    scores.append(max(s[-1] * ((K//length)-1) + smax, s[-1] * (K//length), s[-1] * (K//length) + smodmax))
  else:
    scores.append(smax)
print(max(scores))

Solution (Python):
from itertools import accumulate
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    N, K = map(int, input().split())
    Ps = list(map(lambda x: int(x)-1, input().split()))
    Cs = list(map(int, input().split()))

    cycless = [[] for _ in range(N)]
    useds = [0] * N
    for no in range(N):
        if useds[no]: continue
        x = no
        while True:
            useds[x] = 1
            cycless[no].append(Cs[x])
            x = Ps[x]
            if x == no:
                break




    ans = -float('inf')
    for no in range(N):
        if not cycless[no]: continue
        L = len(cycless[no])
        accCycles = list(accumulate([0]+cycless[no]+cycless[no]+cycless[no]))
        sumC = sum(cycless[no])

        if sumC > 0:
            num = K//L
            if num > 0:
                num -= 1
                if num == 0:
                    fr = 1
                else:
                    fr = 0
                score = -float('inf')
                for M in range(fr, (L + K%L)+1):
                    for st in range(L):
                        s = accCycles[st+M] - accCycles[st]
                        if s > score:
                            score = s
                score += sumC * num
            else:
                score = -float('inf')
                for M in range(1, K+1):
                    for st in range(L):
                        s = accCycles[st+M] - accCycles[st]
                        if s > score:
                            score = s
        else:
            score = -float('inf')
            for M in range(1, (K if K <= L else L)+1):
                for st in range(L):
                    s = accCycles[st+M] - accCycles[st]
                    if s > score:
                        score = s
        if score > ans:
            ans = score


    print(ans)


solve()

Solution (Python):
N,K = (int(T) for T in input().split())
Next = [int(T)-1 for T in input().split()]
GetP = [int(T) for T in input().split()]
DispP = [0]*N
for TN in range(0,N):
    Now   = Next[TN]
    Point = GetP[Now]
    MAXP  = Point
    RoopC = 1
    RoopFlag = False
    for TK in range(1,K):
        Now = Next[Now]
        Point += GetP[Now]
        RoopC += 1
        if Now==TN and Point>=0:
            RoopFlag = True
            break
        elif Now==TN and Point<0:
            RoopFlag = False
            break
        if MAXP<Point:
            MAXP = Point
            MInd = TK
    if RoopFlag:
        Omit = K-RoopC*(K//RoopC)
        PointO = 0
        MAXO = 0
        for TO in range(0,Omit):
            Now = Next[Now]
            PointO += GetP[Now]
            if MAXO<PointO:
                MAXO = PointO
        if Point*(K//RoopC)+MAXO>=Point*((K//RoopC)-1)+MAXP:
            DispP[TN] = Point*(K//RoopC)+MAXO
        else:
            DispP[TN] = Point*((K//RoopC)-1)+MAXP
    else:
        DispP[TN] = MAXP
print(max(DispP))

Solution (Python):
from math import ceil,floor,factorial,gcd,sqrt,log2,cos,sin,tan,acos,asin,atan,degrees,radians,pi,inf
from itertools import accumulate,groupby,permutations,combinations,product,combinations_with_replacement
from collections import deque,defaultdict,Counter
from bisect import bisect_left,bisect_right
from operator import itemgetter
from heapq import heapify,heappop,heappush
from queue import Queue,LifoQueue,PriorityQueue
from copy import deepcopy
from time import time
from functools import reduce
import string
import sys
sys.setrecursionlimit(10 ** 7)
def input() : return sys.stdin.readline().strip()
def INT()   : return int(input())
def MAP()   : return map(int,input().split())
def LIST()  : return list(MAP())

n, k = MAP()
p = LIST()
c = LIST()

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

ans = -inf
for i in range(n):
    visit = [inf]*n
    reg_score = [-inf]*n

    now = i
    count = 0
    score = 0
    while visit[now] == inf:
        visit[now] = count
        reg_score[now] = score
        count += 1
        now = p[now]
        score += c[now]

    x = visit[now]
    y = count - visit[now]
    X = reg_score[now]
    Y = score - reg_score[now]

    for j in range(n):
        if visit[j] == inf:
            continue
        if j != i and k >= visit[j]:
            tmp0 = reg_score[j]
            if ( k - x ) % y >= visit[j]:
                tmp1 = (k - x)//y * Y + reg_score[j]
            else:
                tmp1 = ((k - x)//y - 1) * Y + reg_score[j]
            ans = max(ans, tmp0, tmp1)
        elif (k-x)//y>0:
            tmp0 = Y + reg_score[j]
            if ( k - x ) % y >= visit[j]:
                tmp1 = (k - x)//y * Y + reg_score[j]
            else:
                tmp1 = ((k - x)//y - 1) * Y + reg_score[j]
            ans = max(ans, tmp0, tmp1)

print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 6)
int1 = lambda x: int(x) - 1
p2D = lambda x: print(*x, sep="\n")
def II(): return int(sys.stdin.readline())
def MI(): return map(int, sys.stdin.readline().split())
def LI(): return list(map(int, sys.stdin.readline().split()))
def LI1(): return list(map(int1, sys.stdin.readline().split()))
def LLI(rows_number): return [LI() for _ in range(rows_number)]
def SI(): return sys.stdin.readline()[:-1]

def solve():
    ans = -inf
    for si in range(n):
        cs = [0]
        i = si
        for _ in range(k):
            i = pp[i]
            cs.append(cs[-1] + cc[i])
            if i == si: break
        cur = max(cs[1:])
        if len(cs) < k + 1:
            d = len(cs) - 1
            c = k // d
            r = k - d * c
            cur1=cs[-1] * c + max(cs[:r+1])
            cur2=cs[-1]*(c-1)+max(cs)
            cur = max(cur,cur1,cur2)
        
        ans = max(ans, cur)
    print(ans)

inf=10**16
n,k=MI()
pp=LI1()
cc=LI()
solve()

Solution (Python):
n,k = map(int, input().split())
pp = list(map(lambda x: int(x) - 1, input().split()))
cc = list(map(int, input().split()))

cycles = []
seen = set()
for p in pp:
    i = p
    tmp = []
    while i not in seen:
        v = cc[i]
        tmp.append(v)
        seen.add(i)
        i = pp[i]
    if tmp:
        cycles.append(tmp)

ans = -float('inf')

def calc(resid, cycle):
    if resid == 0:
        return 0
    m = len(cycle)
    dp = [cycle[:]]
    for k in range(1, resid):
        tmp = [0] * m
        for j in range(m):
            tmp[j] = dp[k-1][j] + cycle[(j + k)%m]
        dp.append(tmp)
    mx_resid = max(map(max, dp))
    return mx_resid

for cycle in cycles:
    per_cycle = sum(cycle)
    m = len(cycle)
    if per_cycle > 0:
        cnt_cycle, resid = divmod(k, m)
        mx_resid = calc(resid, cycle)
        ans_cycle = cnt_cycle * per_cycle + mx_resid
        ans = max(ans, ans_cycle)
        
        cnt_cycle = max(0, k // m - 1)
        resid = min(k, m)
        mx_resid = calc(resid, cycle)
        ans_cycle = cnt_cycle * per_cycle + mx_resid
        ans = max(ans, ans_cycle)
    else:
        cnt_cycle = 0
        resid = min(k, m)
        mx_resid = calc(resid, cycle)
        ans_cycle = cnt_cycle * per_cycle + mx_resid
        ans = max(ans, ans_cycle)


print(ans)

Solution (Python):
def main():
    import sys
    N,K=list(map(int,sys.stdin.readline().split()))
    P=list(map(int,sys.stdin.readline().split()))
    C=list(map(int,sys.stdin.readline().split()))

    output=-10**20

    lst=[[0]*(N+1) for _ in range(N)]
    for i in range(N):
        st=set()
        now=i
        count=0
        score=0
        if K==1:
            output=max(output,C[P[i]-1])
            continue

        while True:
            count+=1
            now=P[now]-1

            if now in st:
                count-=1
                break
    
            lst[i][count]=lst[i][count-1]+C[now]
            st.add(now)
            
            if count==K:
                break


        if lst[i][count]>0:
            m=max(lst[i][1:count+1])
            
            if K%count:
                p=max(lst[i][1:K%count+1])
                if p>0:
                    s=lst[i][count]*(K//count)+p
                else:
                    s=lst[i][count]*(K//count-1)+m
            else:
                s=lst[i][count]*(K//count-1)+m
        else:
            s=max(lst[i][1:count+1])
        
        output=max(output,s)

    print(output)

main()

Solution (Python):





import math
import fractions
import sys
import bisect
import heapq  
import collections
from collections import Counter
from collections import deque
import pprint
import itertools

sr = lambda: input()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

"""nを素因数分解"""
"""2以上の整数n => [[素因数, 指数], ...]の2次元リスト"""


def factorization(n):
    arr = []
    temp = n
    if n == 1:
        return arr

    for i in range(2, int(-(-n ** 0.5 // 1)) + 1):
        if temp % i == 0:
            cnt = 0
            while temp % i == 0:
                cnt += 1
                temp //= i
            arr.append([i, cnt])

    if temp != 1:
        arr.append([temp, 1])

    if arr == []:
        arr.append([n, 1])

    return arr



def power(a, n, mod):
    x = 1
    while n:
        if n & 1:
            x *= a % mod
        n >>= 1
        a *= a % mod
    return x % mod



def kaijo(n, l, mod):
    if n == 0:
        return 1
    a = n
    tmp = n - 1
    while (tmp >= l):
        a = a * tmp % mod
        tmp -= 1
    return a


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

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

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

        if x == y:
            return

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

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

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

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

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

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

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

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

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


def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)

    divisors.sort()
    return divisors

inf = 10 ** 18
mod = 10 ** 9 + 7

n,k = lr()
p = lr()
c = lr()
visited = [True for i in range(n)]
ans = -inf

for i in range(n):
    if visited[i]:
        add_list = [i+1]
        visited[i] = False
        tmp = p[i]-1
        pre = 0
        while visited[tmp]:
            pre+=1
            visited[tmp] = False
            add_list.append(tmp+1)
            tmp = p[tmp]-1
        pre_ans = -inf
        length = len(add_list)
        a1 = [0]
        for m in range(2*length):
            a1.append(a1[-1]+c[add_list[m%length]-1])
        pre_total = a1[length]
        full_count = 0
        ret_ind = length

        for ind in range(1, ret_ind+1):
            for m in range(length):
                if ind <= k:
                    tmp = a1[m+ind]-a1[m]
                    pre_ans = max(pre_ans, a1[m+ind]-a1[m])
                    u = (k-ind) // length
                    if pre_total > 0:
                        tmp += (u*pre_total)
                    pre_ans = max(pre_ans, tmp)
        ans = max(ans, pre_ans)
print(ans)

Solution (Python):
from itertools import accumulate
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)

def solve():
    N, K = map(int, input().split())
    Ps = list(map(lambda x: int(x)-1, input().split()))
    Cs = list(map(int, input().split()))

    cycless = [[] for _ in range(N)]
    useds = [0] * N
    for no in range(N):
        if useds[no]: continue
        x = no
        while True:
            useds[x] = 1
            cycless[no].append(Cs[x])
            x = Ps[x]
            if x == no:
                break




    ans = -float('inf')
    for no in range(N):
        if not cycless[no]: continue
        L = len(cycless[no])
        accCycles = list(accumulate([0]+cycless[no]+cycless[no]+cycless[no]))
        sumC = sum(cycless[no])

        if sumC > 0:
            num = K//L
            if num > 1:
                num -= 1
                score = -float('inf')

                for M in range(0, L + K%L+1):
                    for st in range(L):
                        s = accCycles[st+M] - accCycles[st]
                        if s > score:
                            score = s
                score += sumC * num
            else:
                score = -float('inf')
                for M in range(1, K+1):
                    for st in range(L):
                        s = accCycles[st+M] - accCycles[st]
                        if s > score:
                            score = s
        elif sumC == 0:
            num = K//L
            if num > 1:
                score = -float('inf')
                for M in range(0, 2*L+1):
                    for st in range(L):
                        s = accCycles[st+M] - accCycles[st]
                        if s > score:
                            score = s
            else:
                score = -float('inf')
                for M in range(1, K+1):
                    for st in range(L):
                        s = accCycles[st+M] - accCycles[st]
                        if s > score:
                            score = s
        else:
            score = -float('inf')
            for M in range(1, (K if K <= L else L)+1):
                for st in range(L):
                    s = accCycles[st+M] - accCycles[st]
                    if s > score:
                        score = s
        if score > ans:
            ans = score


    print(ans)


solve()

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

data = [[0 for i in range(n+1)] for j in range(n)]
loop = [10**10 for i in range(n)]
for i in range(n):
    j = i
    for t in range(1,n+1):
        j = p[j]
        data[i][t] += data[i][t-1] + c[j]
        if j == i:
            loop[i] = min(loop[i],t)

ans = -10**10



for i in range(n):
    for j in range(1,min(n,k)+1):
        if j > loop[i]:break
        if data[i][loop[i]] <= 0:
            ans = max(ans,data[i][j])
        else:
            ans = max(ans,data[i][loop[i]]*((k-j)//loop[i])+data[i][j])

print(ans)

Solution (Python):
n,k=(map(int,input().split()))
p=list(map(int,input().split()))
c=list(map(int,input().split()))
cnt=list(range(n))
ans=-(10**10)
for i in range(n):
    num=[0]
    num11=[]
    num2=p[cnt[0]]-1
    num3=cnt[0]
    cnt.remove(cnt[0])
    for j in range(n+1):
        cnt10=c[num2]
        num.append(num[-1]+cnt10)
        num11.append(cnt10)
        if num2==num3:
            break
        cnt.remove(num2)
        num2=p[num2]-1
    lnum=len(num)-1
    for j in range(lnum):
        num.append(num[-1]+num11[j])
    if num[-1]<0 or k<lnum:
        ans2=-(10**10)
        for j in range(lnum):
            cnt2=num[j]
            num10=0
            for l in range(min(lnum,k)):
                ans2=max(ans2,num[j+l+1]-cnt2)
        ans=max(ans,ans2)
    else:
        ans3=-(10**10)
        ans4=0
        ans5=-(10**10)
        for j in range(lnum):
            cnt2=num[j]
            num10=0
            num14=k%lnum
            for l in range(lnum):
                ans3=max(ans3,num[j+l+1]-cnt2)
                if num14>l:
                    ans5=max(ans5,num[j+l+1]-cnt2)
        ans6=k//lnum
        ans=max(ans,(ans6*num[lnum])+ans5,((ans6-1)*num[lnum])+ans3)
    if len(cnt)==0:
        break
print(ans)

Solution (Python):
import sys
from itertools import accumulate

input = sys.stdin.readline


class UnionFind:
    """Union Find class.

    "Path compression" and "Union by rank" are used.

    References:
        <https://en.wikipedia.org/wiki/Disjoint-set_data_structure>
    """

    def __init__(self, N):
        self.N = N
        self.__make_set()

    def __make_set(self):
        self._parent = list(range(self.N + 1))
        self._rank = [0] * (self.N + 1)
        self._size = [1] * (self.N + 1)

    def find(self, x):
        if self._parent[x] != x:
            self._parent[x] = self.find(self._parent[x])
        return self._parent[x]

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

        if x_root == y_root:
            return

        x_rank = self._rank[x_root]
        y_rank = self._rank[y_root]
        if x_rank > y_rank:
            self._parent[y_root] = x_root
            self._size[x_root] += self._size[y_root]
        elif x_rank < y_rank:
            self._parent[x_root] = y_root
            self._size[y_root] += self._size[x_root]
        else:
            self._parent[y_root] = x_root
            self._rank[x_root] += 1
            self._size[x_root] += self._size[y_root]

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

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


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

    uf = UnionFind(N)
    for i, p in enumerate(P, 1):
        uf.union(i, p)

    ans = -float("inf")
    visited_cc = set()
    for i in range(1, N + 1):
        cc = uf.find(i)
        if cc in visited_cc:
            continue
        visited_cc.add(cc)

        CC = []
        j = P[i - 1]
        while True:
            CC.append(C[j - 1])
            if i == j:
                break
            j = P[j - 1]
        n_CC = len(CC)
        loop_cost = sum(CC)
        CC = list(accumulate([0] + CC * 2))

        if K < n_CC:
            cost = [-float("inf")] * n_CC
            for n_move in range(1, K + 1):
                for j in range(n_CC):
                    tmp = CC[j + n_move] - CC[j]
                    cost[n_move - 1] = max(cost[n_move - 1], tmp)
            res = max(cost)
        else:
            cost = [-float("inf")] * n_CC
            for n_move in range(1, n_CC):
                for j in range(n_CC):
                    tmp = CC[j + n_move] - CC[j]
                    cost[n_move - 1] = max(cost[n_move - 1], tmp)
            q, r = divmod(K, n_CC)
            if loop_cost > 0:
                if r > 0:
                    res = max(loop_cost * q + max(cost[:r]), loop_cost * (q - 1) + max(cost))
                else:
                    res = max(loop_cost * q, loop_cost * (q - 1) + max(cost))
            else:
                res = max(cost)

        ans = max(ans, res)

    print(ans)


if __name__ == "__main__":
    main()

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









visited = [False]*(N+1)
loops = []
for v in range(1,N+1):
    if visited[v]:
        continue
    l = [v]
    while True:
        v = l[-1]
        visited[v] = True
        nv = P[v-1]
        if visited[nv]:
            break
        l.append(nv)
    loops.append(l)

cand = []
for loop in loops:
    temp = 0
    vals = [C[i-1] for i in loop]
    l = len(vals)
    vals3 = vals+vals+vals[:-1]
    cumsum = [0]
    for v in vals3:
        cumsum.append(cumsum[-1] + v)
    gh = []
    
    if K <= l:
        temp = 0
        ma = min(vals)
        for left in range(0,2*l-K):
            for right in range(left+1,left+K+1):
                ma = max(ma,(cumsum[right] - cumsum[left]))
        temp += ma
    else:
        temp = 0
        s = sum(vals)
        q, r = divmod(K,l)
        q -= 1
        r += l
        ma = min(vals)
        for left in range(0,3*l-r):
            for right in range(left+1,left+r+1):
                ma = max(ma,(cumsum[right] - cumsum[left]))
        temp += ma
        if s > 0:
            temp += q * s
    cand.append(temp)
print(max(cand))