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):
import collections
def main():

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

    ans = float('-inf')
    if K <= N:
        for i in range(N):
            v = 0
            k = i
            for j in range(K):
                k = P[k]-1
                v += C[k]
                ans = max(ans, v)
        return ans

    for i in range(N):
        visited = dict()
        k = i
        visited[i] = 0
        val = [0]
        v = 0
        for j in range(1, N+1):
            k = P[k] - 1
            if k not in visited:
                visited[k] = j
                val.append(C[k])
                v += C[k]
                ans = max(ans, v)
            else:
                m = visited[k]
                t = j - m
                val.append(C[k])
                v += C[k]
                ans = max(ans, v)
                
                val1 = val[:m+1]
                val2 = val[m+1:]
                period = sum(val2)
                pre = sum(val1)
                n = (K - m) // t
                rem = (K-m) % t
                u = 0
                ans = max(ans, u + pre + period * n)
                for p in range(rem):
                    u += val2[p]
                    ans = max(ans, u + pre + period * n)
                u = 0
                for p in range(t):
                    u += val2[p]
                    ans = max(ans, u + pre + period * (n-1))
                break

    return ans


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

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

ans = -float("inf")
for i in range(1, N+1):
    S = i
    visited = [False for i in range(N+1)]
    point = []
    while visited[S] == False:
        point.append(C[S])
        visited[S] = True
        S = P[S]

    L = len(point)
    index = 0
    for i in range(L):
        if point[i] == C[S]:
            index = i
            break

    not_loop = index
    loop = L-index
    Loop = point[index:]
    B = 0
    for i in range(index, L):
        B += point[i]
    if B > 0:
        if not_loop > K:
            D = 0
            for i in range(K):
                D += point[i]
                ans = max(D, ans)

        if not_loop <= K:
            D = 0
            for i in range(not_loop):
                D += point[i]
            K -= not_loop
            for i in range(1, loop):
                Loop[i] += Loop[i-1]
            for i in range(1, loop):
                Loop[i] = max(Loop[i], Loop[i-1])
            if K % loop == 0:
                ans = max(ans, D+B*(K//loop-1)+Loop[-1])
            elif K % loop != 0:
                ans = max(ans, D+B*(K//loop-1) +
                          Loop[-1], D+B*(K//loop)+Loop[K % loop-1])

    else:
        ans = max(point[0], ans)
        for i in range(1, min(L, K)):
            point[i] += point[i-1]
            ans = max(point[i], ans)


print(ans)

Solution (Python):
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
s=[[0 for _ in range(2)] for _ in range(n)]
for i in range(n):
    cnt=0
    now=i
    while True:
        now=(p[now]-1)
        s[i][0]+=c[now]
        cnt+=1
        if now==i:
            break
    s[i][1]=cnt
ans=-(10**16)
for j in range(n):
    if s[j][0]>0 and k//s[j][1]>0: 
        cnt1,cnt2=k,k
        a=k//s[j][1] 
        score1=(a*s[j][0])
        score2=((a-1)*s[j][0])
        cnt1-=a*s[j][1]
        now=j
        pscore1=0
        pscore_max1=0
        for x in range(cnt1):
            now=(p[now]-1)
            pscore1+=c[now]
            pscore_max1=max(pscore_max1,pscore1)
        score1+=pscore_max1
        now=j
        pscore2=0
        pscore_max2=0
        for y in range(s[j][1]):
            now=(p[now]-1)
            pscore2+=c[now]
            pscore_max2=max(pscore_max2,pscore2)
        score2+=pscore_max2
        score_max=max(score1,score2)
    else:
        now=j
        score=0
        score_max=c[p[now]-1]
        for x in range(min(k,s[j][1])):
            now=(p[now]-1)
            score+=c[now]
            score_max=max(score_max,score)
    ans=max(ans,score_max)
print(ans)

Solution (Python):

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


def cycle(v):
    check=[False for _ in range(n+1)]
    check[v]=True
    while True:
        v=P[v]
        if check[v]:
            return v
        else:
            check[v]=True

ans=-1*float("inf")
for v in range(1,n+1):
    point=0
    tans=-1*float("inf")
    m=0
    st=cycle(v)

    while v!=st and m<k:
        m+=1
        v=P[v]
        point+=C[v]
        tans=max(tans,point)

    if m==k:
        ans=max(ans,tans)
        continue
       
    c_point=0
    t=0
    while True:
        t+=1
        v=P[v]
        c_point+=C[v]
        if v==st:
            break
    cp=0
    cpmax=-1*float("inf")
    if 2*t>k-m:
        v=st
        for _ in range(k-m):
            v=P[v]
            cp+=C[v]
            cpmax=max(cpmax,cp)
        tans=point+cpmax
        ans=max(ans,tans)
 

    elif c_point>0:
        l=(k-m)//t
        mv=k-m-(l-1)*t
        cp=c_point*(l-1)
        v=st
        for _ in range(mv):
            v=P[v]
            cp+=C[v]
            cpmax=max(cpmax,cp)
        tans=point+cpmax
        ans=max(ans,tans)

    else:
        v=st
        for _ in range(t):
            v=P[v]
            cp+=C[v]
            cpmax=max(cpmax,cp)
        tans=point+cpmax
        ans=max(ans,tans)
print(ans)

Solution (Python):
n,k = map(int,input().split())
p = list(map(int,input().split()))
for i in range(n):
    p[i]-=1
c = list(map(int,input().split()))
par = [-1 for i in range(n)]
deep = [1 for i in range(n)]
ma = max(c)
def find(x):
    if par[x] < 0:
        return x
    else:
        par[x] = find(par[x])
        return par[x]
def unite(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        return False
    else:
        if deep[x] > deep[y]:
            par[x] += par[y]
            par[y] = x
        elif deep[x] < deep[y]:
            par[y] += par[x]
            par[x] = y
        else:
            par[x] += par[y]
            par[y] = x
            deep[x] += 1
        return True
def same(x,y):
    return find(x) == find(y)
def size(x):
    return -par[find(x)]
for i in range(n):
    unite(i,p[i])
for i in range(n):
    if par[i] >= 0:
        continue
    else:
        t = -par[i]
        if t >= k:
            for j in range(k):
                tmp = 0
                tmp2 = p[i]
                for l in range(j+1):
                    tmp += c[tmp2]
                    tmp2 = p[tmp2]
                tmp3 = p[i]
                ma = max(ma,tmp)
                for l in range(t):
                    tmp += c[tmp2]
                    tmp -= c[tmp3]
                    tmp2 = p[tmp2]
                    tmp3 = p[tmp3]
                    ma = max(ma,tmp)
        else:
            tmpp = p[i]
            tmp7 = 0
            for j in range(t):
                tmp7 += c[tmpp]
                tmpp = p[tmpp]
            if tmp7 <= 0:
                for j in range(t):
                    tmp = 0
                    tmp2 = p[i]
                    for l in range(j+1):
                        tmp += c[tmp2]
                        tmp2 = p[tmp2]
                    tmp3 = p[i]
                    ma = max(ma,tmp)
                    for l in range(t):
                        tmp += c[tmp2]
                        tmp -= c[tmp3]
                        tmp2 = p[tmp2]
                        tmp3 = p[tmp3]
                        ma = max(ma,tmp)
            else:
                g = k//t
                g2 = k//t - 1
                ma2 = 0
                ma3 = 0
                for j in range(k % t):
                    tmp = 0
                    tmp2 = p[i]
                    for l in range(j+1):
                        tmp += c[tmp2]
                        tmp2 = p[tmp2]
                    tmp3 = p[i]
                    ma2 = max(ma2,tmp)
                    for l in range(t):
                        tmp += c[tmp2]
                        tmp -= c[tmp3]
                        tmp2 = p[tmp2]
                        tmp3 = p[tmp3]
                        ma2 = max(ma2,tmp)
                ma2 += tmp7 * g
                for j in range(t):
                    tmp = 0
                    tmp2 = p[i]
                    for l in range(j+1):
                        tmp += c[tmp2]
                        tmp2 = p[tmp2]
                    tmp3 = p[i]
                    ma3 = max(ma3,tmp)
                    for l in range(t):
                        tmp += c[tmp2]
                        tmp -= c[tmp3]
                        tmp2 = p[tmp2]
                        tmp3 = p[tmp3]
                        ma3 = max(ma3,tmp)
                ma3 += tmp7 * g2
                ma = max(max(ma,ma2),ma3)
print(ma)

Solution (Python):
N, K = [int(x) for x in input().split()]
temp = [int(x) for x in input().split()]
p = [-1]
for x in temp:
    p.append(x)
c = [-1]
temp = [int(x) for x in input().split()]
 
for x in temp:
    c.append(x)
 



ans = -int(1e12)
for i in range(1, N+1):
    ans = max(ans, c[p[i]])

for i in range(1, N+1):
    
    visited = [False] * (N+1)
    cur_sum = 0
    cur_box = i
    l = 0
    k = K
    while k > 0:
        if visited[cur_box]:
            break
        cur_sum += c[p[cur_box]]
        ans = max(ans, cur_sum)
        visited[cur_box] = True
        cur_box = p[cur_box]
        k -= 1
        l += 1
        
    if k != 0 and cur_sum > 0:
        cur_sum = (cur_sum * ((K // l)-1))
        ans = max(ans, cur_sum)
        k = (K % l) + l
        while k > 0:
            cur_sum += c[p[cur_box]]
            ans = max(ans, cur_sum)
            cur_box = p[cur_box]
            k -= 1
            
    
    
print(ans)

Solution (Python):
from collections import defaultdict
inpl = lambda: list(map(int,input().split()))
class UnionFind:
    def __init__(self, N=None):
        if N is None or N < 1:
            self.parent = defaultdict(lambda: -1)
        else:
            self.parent = [-1]*int(N)

    def root_rec(self, n):
        if self.parent[n] < 0:
            return n
        else:
            m = self.root(self.parent[n])
            self.parent[n] = m
            return m

    def root(self, n):
        stack = []
        while n >= 0:
            stack.append(n)
            n = self.parent[n]
        m = stack.pop()
        while stack:
            self.parent[stack.pop()] = m
        return m

    def merge(self, m, n):
        rm = self.root(m)
        rn = self.root(n)
        if rm != rn:
            if -self.parent[rm] < -self.parent[rn]:
                rm, rn = rn, rm
            self.parent[rm] += self.parent[rn]
            self.parent[rn] = rm

    def size(self, n):
        return -self.parent[self.root(n)]
    
    def connected(self, m, n):
        return self.root(m) == self.root(n)

    def groups(self):
        if isinstance(self.parent,list):
            return list(filter(lambda i: self.parent[i]<0, range(len(self.parent))))
        else: 
            return list(filter(lambda i: self.parent[i]<0, self.parent.keys()))
 
    def groups_num(self):
        return len(self.groups())

    def elements(self):
        if isinstance(self.parent,list):
            return range(len(self.parent))
        else:
            return self.parent.keys()

N, K = inpl()
P = list(map(lambda x: x-1,inpl()))
C = inpl()

uf = UnionFind(N)
for i in range(N):
    uf.merge(i, P[i])

ans = C[0]
for g in uf.groups():
    L = uf.size(g)
    cycle = C[g]
    p = P[g]
    while p != g:
        cycle += C[p]
        p = P[p]
    q, r = K//L, K % L
    if cycle > 0:
        score = q * cycle
    else:
        score = 0

    s = g
    for _ in range(L):
        u = score
        t = s
        for i in range(L):
            u += C[t]
            t = P[t]
            if i == r:
                if q > 0 and cycle > 0:
                    u -= cycle
                elif q > 0 and cycle <= 0:
                    pass
                elif q == 0:
                    break
            if u > ans:
                ans = u
        s = P[s]

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
  tmp = []
  j = i
  while j not in visited:
    tmp.append(C[j])
    visited.add(j)
    j = P[j]
  
  M = len(tmp)
  L = max(0,sum(tmp))
  now = L * (K // M)
  k = K % M
  tmp2 = 0
  tmp4 = 0
  for l in range(1,min(M,K)+1):
    tmp2 += tmp[l-1]
    tmp3 = tmp2
    for j in range(M):
      tmp4 = max(tmp4, tmp3) 
      tmp3 += tmp[(j+l)%M] - tmp[j%M]
      
      ans = max(ans, now+tmp4 if l <= k else now+tmp4-L)
  
  
  del tmp

flag = True
for c in C:
  if c > 0:
    flag = False
    
print(max(C) if flag else ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**8)
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 li2(N): return [list(map(int, sys.stdin.readline().split())) for i in range(N)]
def dp2(ini, i, j): return [[ini]*i for i2 in range(j)]



from itertools import accumulate 

N, K = mi()
P = li()
C = li()
ans = -float('inf')

for i in range(N):
    ind = i
    his = []
    while True:
        ind = P[ind] - 1
        his.append(C[ind])
        if ind == i:
            his = list(accumulate(his))
            
            L = len(his)
            if K > L:
                if his[-1] > 0:
                    if not K%L:
                        ans = max(ans, his[-1] * (K//L), max(his) + his[-1] * max(K//L-1, 0))
                    else:
                        ans = max(ans, max(his[:K%L]) + his[-1] * (K//L), his[-1] * (K//L), max(his) + his[-1] * max(K//L-1, 0))
                else:
                    ans = max(ans, max(his))
            else:
                ans = max(ans, max(his[:K]))
            break

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()
    seen = [0] * n
    ans = max(c)
    for i in range(n):
        if seen[i]:
            continue
        g = list()
        v = i
        while not seen[v]:
            g.append(c[v])
            seen[v] = 1
            v = p[v] - 1
        m = len(g)
        for i in range(1, m):
            g[i] += g[i-1]
        if k <= m:
            for i in range(m):
                for j in range(i+1, i+k+1):
                    cur = 0
                    if j >= m:
                        cur += g[-1]
                        j -= m
                    cur += g[j] - g[i]
                    if ans < cur:
                        ans = cur
        else:
            for i in range(m):
                for j in range(i+1, i+m+1):
                    cur = 0
                    if g[-1] > 0:
                        cur += g[-1] * ((k - (j-i))//m)
                    if j >= m:
                        cur += g[-1]
                        j -= m
                    cur += g[j] - g[i]
                    if ans < cur:
                        ans = cur
    print(ans)
    return

solve()

Solution (Python):



def mp(): return map(int, input().split())
def lmp(): return list(map(int, input().split()))

n,k = mp()
p = lmp()
p = [p[i]-1 for i in range(n)]
c = lmp()


def cum_sum(lst):
    cums = [0] * (len(lst)+1)
    cums[1] = lst[0]
    for i in range(2,len(lst)+1):
        cums[i] = cums[i-1] + lst[i-1]
    return cums

ans = -int(1e18)-5
for i in range(n):
    now = p[i]
    sc = [c[now]]
    cnt = 1
    while now != i:
        now = p[now]
        sc.append(c[now])
        cnt += 1
    cums = cum_sum(sc)[1:]
    if k <= len(cums):
        cums = cums[:k]
        ans = max(ans, max(cums))
    else:
        if cums[-1] <= 0:
            ans = max(ans, max(cums))
        else:
            lop = k // len(cums)
            u = [cums[j]+(lop-1)*cums[-1] for j in range(len(cums))] + [cums[j]+lop*cums[-1] for j in range(k%len(cums))]
            ans = max(ans,max(u))
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()))
res = [0] * N
for i in range(N):
  x = i
  score = -float("inf")
  loopscore = 0
  loop = 0
  while x != i or loop == 0:
    loop += 1
    x = p[x] - 1
    loopscore += c[x]
    if loop <= K: score = max(score, loopscore)
  
  if loopscore <= 0:
    res[i] = score
  else:
    res[i] = K // loop * loopscore
    
    plus = 0
    plusmx = 0
    x = i
    t = 0
    while t < K % loop:
      t += 1
      x = p[x] - 1
      plus += c[x]
      plusmx = max(plusmx, plus)
    res[i] += plusmx
    if K >= loop: res[i] = max(res[i], (K // loop - 1) * loopscore + score)

print(max(res))

Solution (Python):
n,k = map(int,input().split())
p = [0] + list(map(int,input().split()))
c = [0] + list(map(int,input().split()))
ans = max(c[1:])
t = 0
for i in range(1,n+1):
    
    j = p[i]
    temp = c[i]
    cnt = 1
    ans = max(ans,temp)
    tempans = 0
    while i!=j:
        
        temp += c[j]
        j = p[j]
        cnt += 1
        
        
    t = cnt
    tt = ans
    
    
    if t < k:
        if temp > 0:
            
            tempans += temp*(k//t - 1)
            tt = tempans
            j = p[i]
            for l in range(k-(k//t - 1)*t):
                tempans += c[j]
                j = p[j]
                tt = max(tt,tempans)
            ans = max(ans,tt)
            
        else:
            j = p[i]
            for l in range(t):
                tempans += c[j]
                j = p[j]
                tt = max(tt,tempans)
            ans = max(ans,tt)
            
    else:
        j = p[i]
        for l in range(k):
            tempans += c[j]
            j = p[j]
            tt = max(tt,tempans)
        ans = max(ans,tt)
        
    
    
    
print(ans)

Solution (Python):
N, K = map(int,input().split())
P = list(map(int,input().split()))
C = list(map(int,input().split()))
ans = max(C)
for i in range(N):
    check = {i}
    loop_score =[]
    k = i
    while True:
        loop_score.append(C[k])
        k = P[k]-1
        t = len(check)
        check.add(k)
        if len(check)==t:
            break
    cum_score = 0
    cum_scores = []
    for j in loop_score:
        cum_score+=j
        cum_scores.append(cum_score)
    loop = cum_scores[-1]
    compare = min(0,max(cum_scores))
    loops = K//len(cum_scores)
    plus = K%len(cum_scores)
    if loop > 0:
        compare = 0
        compare+=loops*loop
    final = cum_scores[:plus]
    if plus != 0:
        compare+=max(final)
        
    if loop > 0:
        compare2 = max(cum_scores) + (loops-1)*loop
        if compare2 > compare:
            compare = compare2

    if K < len(cum_scores):
        cum_scores = cum_scores[:K]
    if max(cum_scores)>compare:
        compare = max(cum_scores)
    if compare>ans and compare!=0:
        ans = compare
print(ans)

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

def I(): return int(input())
def MI(): return map(int, input().split())
def LI(): return list(map(int, input().split()))

def main():
    
    class UnionFind():
        """
        parents : 親要素(findしない場合は根ではないことの注意)，根の場合は"-(要素数）"
        find(x):要素xの属するグループの根を返す
        size(x):要素xの属するグループの要素数を返す
        same(x,y):x,yが同じグループに属しているか返す
        重いかも！　　members(x):要素xが属するグループに属する要素をリストで返す
        roots:全ての根の要素を返す
        group_count():グループの数を返す
        重いかも！　all_group_members():{根要素：[そのグループに含まれる要素のリスト]}の辞書を返す
        """
        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())

    


    mod=10**9+7
    N,K=MI()
    P=LI()
    C=LI()
    
    for i in range(N):
        P[i]-=1
    
    uf =UnionFind(N)
    for i in range(N):
        uf.union(i,P[i])
        
    from collections import defaultdict
    dd = defaultdict(list)
        
    for i in range(N):
        root=uf.find(i)
        dd[root]+=[i]
        
    ansAll=-1*(10**10)
    for k,v in dd.items():
        N2=len(v)
        
        L=[0]*(3*N2+3)
        now=k
        for i in range(3*N2+3):
            nxt=P[now]
            L[i]=C[nxt]
            now=nxt
        S=[0]*(3*N2+3)
        for i in range(3*N2+2):
            S[i+1]=S[i]+L[i]
        
        ans=0
        
        ROOP=S[N2]-S[0] 
        if ROOP>0:
            roop=max(K//N2-1,0)
            ans+=ROOP*roop
            rem=K-roop*N2
        else:
            roop=0
            rem=min(K,N2)
            
        if roop==0:
            temp=-1*(10**10)
        else:
            
            temp=0
        for i in range(1,rem+1):
            for j in range(N2+1):
                s=S[j+i]-S[j]
                temp=max(temp,s)
        ans=ans+temp
        
        
        
        
        
        
        
        
        ansAll=max(ansAll,ans)
        
    print(ansAll)
        
            
    
 
        
    
            
    

main()

Solution (Python):
from itertools import accumulate


def solve():
    N, K = map(int, input().split())
    P = list(map(int, input().split()))
    L = list(map(int, input().split()))

    ans = -float("inf")
    for i in range(N):
        score_acc = [L[i]]
        cur = P[i] - 1
        while cur != i:
            score_acc.append(L[cur])
            cur = P[cur] - 1
        score_acc = list(accumulate(score_acc))
        M = len(score_acc)
        if M < K and score_acc[-1] > 0:
            res = K // M * score_acc[-1]
            if K % M:
                res += max(score_acc[: K % M])
            else:
                res += -score_acc[-1] + max(score_acc)
            ans = max(ans, res)
        else:
            res = max(score_acc[:K])
            ans = max(ans, res)
    return ans


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):
    s = 0
    j = i
    for k in range(K):
        j = P[j]-1
        s += C[j]
        ans = max(ans, s)
        if j==i: break
    d,m = divmod(K, k+1)
    if m==0 and d>1:
        m = k+1
        d -= 1
    s *= d
    ans = max(ans, s)
    for k in range(m):
        j = P[j]-1
        s += C[j]
        ans = max(ans, s)

print(ans)

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

visited = [False]*N
lp = [[0] for _ in range(N)]

lidx = 0
for s in range(N):
    if visited[s]:
        continue

    nex = s
    while not visited[nex]:
        visited[nex] = True
        now = P[nex]
        nex = now
        lp[lidx].append(lp[lidx][-1] + C[now])

    lidx += 1

ans = -(10**10)

for k in range(lidx):
    loop = lp[k]
    km = loop[-1]
    
    lenloop = len(loop)-1

    pt = 0

    kk = K

    x = max(kk//lenloop-1, 0)
    if km > 0:
        pt += x*km
    kk -= x*lenloop

    

    for i in range(lenloop*2):
        loop.append(loop[i+1]+km)
    
    for i in range(lenloop):
        for j in range(i+1, i+kk+1):
            
            ans = max(loop[j]-loop[i]+pt, ans)



print(ans)

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

mx = [0] * N
cnts = [0] * N
for i in range(N):
  if mx[i] == 0:
    nxt = P[i]-1
    tmp = 0
    l = [nxt]
    for j in range(N):
      tmp += C[nxt]
      nxt = P[nxt]-1
      l.append(nxt)
      if nxt == i:
        tmp += C[nxt]
        cnt = j+2
        break
    for k in l:
      cnts[k] = cnt
      n = ((K//cnt)-1) * tmp
      if tmp > 0:
        mx[k] += n
    
for i in range(N):
  nxt = P[i]-1
  tmp = 0
  m = min(C) - 1
  for j in range((K%cnts[i])+cnts[i]):
    tmp += C[nxt]
    m = max(m, tmp)
    nxt = P[nxt]-1
  mx[i] += m

ans = max(mx)
print(ans)

Solution (Python):
n,k = map(int,input().split())
p = [int(i)-1 for i in input().split()]
c = [int(i) for i in input().split()]
INF = float("INF")
ans = -INF
for i in range(n):
    flag = [False]*n
    now = i
    cnt = 0
    j = 0
    mlst = [-INF]*n
    m = -INF
    while not flag[now]:
        flag[now] = True
        now = p[now]
        cnt += c[now]
        m = max(cnt,m)
        mlst[j] = m
        j += 1
    
    q,r = divmod(k,j)
    if q == 0: res = mlst[r-1]
    elif cnt >= 0 and r == 0: res = cnt*(q-1)+mlst[j-1]
    elif cnt >= 0: res = max(cnt*q+mlst[r-1],cnt*(q-1)+mlst[j-1])
    else: res = mlst[j-1]
    
    ans = max(ans,res)
print(ans)

Solution (Python):
n, k = [int(i) for i in input().split()]
p = [int(i) for i in input().split()]
c = [int(i) for i in input().split()]
m = -1 * 10 ** 9 
for i in range(1, n+1):
    place = p[i-1]
    sm = [c[place-1]]
    while place != i:
        place = p[place-1]
        sm += [c[place-1] + sm[-1]]

    if len(sm) < k:
        m = max(m, 
            max(max(sm), 
                sm[-1] * ((k-1) // len(sm)) + sm[min((k-1) % len(sm), sm.index(max(sm)))]
                )
        )
    else:
        for j in range(k):
            m = max(m, sm[j])

print(m)

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 = -1 * 2 ** 30

if K <= N:
    for i in range(N):
        pos = i
        score = 0
        for j in range(K):
            score += C[pos]
            pos = P[pos]
            ans = max(ans, score)
    print(ans)
    exit(0)

for i in range(N):
    pos = i
    k = 0
    score = 0

    for j in range(N):
        score += C[pos]
        pos = P[pos]
        ans = max(ans, score)
        k += 1
        if pos == i:
            break

    score *= (K // k) - 1
    ans = max(ans, score)
    for j in range(k + (K % k)):
        score += C[pos]
        pos = P[pos]
        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()))
raw = []
seen = [0 for _ in range(n)]
for i in range(n):
  now = int(i)
  tmp = []
  if seen[i]:
    continue
  while seen[now] == 0:
    tmp.append(c[now])
    seen[now] = 1
    now = p[now] - 1
  raw.append(tmp)

can = 0
for x in raw:
  sun = sum(x)
  l = len(x)
  x = x + x + x
  
  now = [0]
  for y in x:
    now.append(now[-1]+y)
  
  if sun > 0 and k >= l:
    ans = sun * (k//l-1)
    K = k % l + l
    
    maxi = 0
    for i in range(l):
      for j in range(i+1,3*l+1):
        if j - i <= K:
          maxi = max(maxi,now[j]-now[i])
    can = max(ans+maxi,can)
    
  else:
    maxi = 0
    for i in range(3*l+1):
      for j in range(i+1,3*l+1):
        if j - i <= k:
          maxi = max(maxi,now[j]-now[i])
    can = max(maxi,can)
    
    
if can == 0:
  print(max(c))
else:
  print(can)