Problem:
 Score : 400 points    Problem Statement Takahashi will play a game using a piece on an array of squares numbered 1, 2, \cdots, N . Square i has an integer C_i written on it. Also, he is given a permutation of 1, 2, \cdots, N : P_1, P_2, \cdots, P_N .  Now, he will choose one square and place the piece on that square. Then, he will make the following move some number of times between 1 and K (inclusive):   In one move, if the piece is now on Square i  (1 \leq i \leq N) , move it to Square P_i . Here, his score increases by C_{P_i} .   Help him by finding the maximum possible score at the end of the game. (The score is 0 at the beginning of the game.)      Constraints  2 \leq N \leq 5000  1 \leq K \leq 10^9  1 \leq P_i \leq N  P_i \neq i  P_1, P_2, \cdots, P_N are all different.  -10^9 \leq C_i \leq 10^9  All values in input are integers.         Input Input is given from Standard Input in the following format:  N  K  P_1  P_2  \cdots  P_N  C_1  C_2  \cdots  C_N       Output Print the maximum possible score at the end of the game.        Sample Input 1 5 2
2 4 5 1 3
3 4 -10 -8 8      Sample Output 1 8  When we start at some square of our choice and make at most two moves, we have the following options:   If we start at Square 1 , making one move sends the piece to Square 2 , after which the score is 4 . Making another move sends the piece to Square 4 , after which the score is 4 + (-8) = -4 .  If we start at Square 2 , making one move sends the piece to Square 4 , after which the score is -8 . Making another move sends the piece to Square 1 , after which the score is -8 + 3 = -5 .  If we start at Square 3 , making one move sends the piece to Square 5 , after which the score is 8 . Making another move sends the piece to Square 3 , after which the score is 8 + (-10) = -2 .  If we start at Square 4 , making one move sends the piece to Square 1 , after which the score is 3 . Making another move sends the piece to Square 2 , after which the score is 3 + 4 = 7 .  If we start at Square 5 , making one move sends the piece to Square 3 , after which the score is -10 . Making another move sends the piece to Square 5 , after which the score is -10 + 8 = -2 .   The maximum score achieved is 8 .       Sample Input 2 2 3
2 1
10 -7      Sample Output 2 13       Sample Input 3 3 3
3 1 2
-1000 -2000 -3000      Sample Output 3 -1000  We have to make at least one move.       Sample Input 4 10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719      Sample Output 4 29507023469  The absolute value of the answer may be enormous.

Solution (Python):
def main():
    from itertools import accumulate as ac
    n, k = map(int, input().split())
    p = list(map(int, input().split()))
    c = list(map(int, input().split()))
    s = set()
    loop = []
    for i in range(n):
        if i not in s:
            j = i
            temp = [c[j]]
            s.add(j)
            while True:
                j = p[j]-1
                if j not in s:
                    temp.append(c[j])
                    s.add(j)
                else:
                    break
            loop.append(temp+temp)
    ans = -10**15
    for l in loop:
        m = len(l)//2
        s = max(0, sum(l)//2)
        l = [0]+list(ac(l))
        temp = [-10**15]*m
        for i in range(m):
            for j in range(i+1, i+m+1):
                width = j-i-1
                temp[width] = max(temp[width], l[j]-l[i])
        for i in range(m):
            if k-i-1 >= 0:
                ans = max(ans, ((k-i-1) // m)*s+temp[i])
    print(ans)


main()

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

ans=float('inf')*-1

for i in range(n):
    visited=[i]
    pin=0
    now=i
    for j in range(k):
        now=p[now]-1
        pin+=c[now]
        ans=max(ans,pin)
        visited+=[now]

        if visited[0]==visited[-1]:
            if pin>0:
                pin*=(k//(len(visited)-1)-1)
                ans=max(ans,pin)

                for s in range(k%(len(visited)-1)+len(visited)-1):
                    now=p[now]-1
                    pin+=c[now]
                    ans=max(ans,pin)

                break

            else:
                break

print(ans)

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

LC = [-1] * N



max_score = -float('inf')
for i in range(N):
    Loop_len = 0
    Loop_cost =[]
    Loop_cost_sum = 0
    now = i
    while True:
        now = P[now] - 1
        Loop_len += 1
        Loop_cost_sum += C[now]
        Loop_cost.append(Loop_cost_sum)
        if now == i:
            break
    
    for i,lc in enumerate(Loop_cost):
        if K-(i+1)<0: 
            continue
        possible_loop_num = (K-(i+1))//Loop_len
        cost = lc + max(0,Loop_cost_sum) * possible_loop_num
        max_score = max(cost,max_score)

print(max_score)

Solution (Python):
from itertools import accumulate


def main():
    cells, can_jump = [int(x) for x in input().split()]
    jumps_from = [int(x) - 1 for x in input().split()]
    score_on = [int(x) for x in input().split()]

    ans = - 10**10
    for start in range(cells):
        route = []
        position = start
        while True:
            route.append(score_on[position])
            position = jumps_from[position]
            if position == start:  
                break

        length = len(route)
        total = sum(route)
        for jumping, accum_candidate in enumerate(accumulate(route)):
            jumping += 1
            if jumping > can_jump:
                break
            if total > 0:
                accum_candidate += total * ((can_jump - jumping) // length)
            ans = max(ans, accum_candidate)
    return ans


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

Solution (Python):
def main():
    cells, can_jump = [int(x) for x in input().split()]
    jumps_from = [int(x) - 1 for x in input().split()]
    score_on = [int(x) for x in input().split()]

    ans = - 10**10
    for start in range(cells):
        route = []
        position = start
        while True:
            route.append(score_on[position])
            position = jumps_from[position]
            if position == start:  
                break

        length = len(route)
        total = sum(route)
        accum = 0
        for jumping, score in enumerate(route):
            jumping += 1
            accum += score
            if jumping > can_jump:
                break
            candidate = accum
            if total > 0:
                candidate += total * ((can_jump - jumping) // length)
            ans = max(ans, candidate)
    return ans


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

Solution (Python):
def main():
    cells, can_jump = [int(x) for x in input().split()]
    jumps_from = [int(x) - 1 for x in input().split()]
    score_on = [int(x) for x in input().split()]

    ans = - 10**10
    for start in range(cells):
        route = []
        position = start
        while True:
            route.append(score_on[position])
            position = jumps_from[position]
            if position == start:  
                break

        length = len(route)
        total = sum(route)
        accum_tmp = 0
        for jumping, score in enumerate(route):
            accum_tmp += score
            if jumping + 1 > can_jump:
                break
            accum = accum_tmp
            if total > 0:
                accum += total * ((can_jump - (jumping + 1)) // length)
            ans = max(ans, accum)
    return ans


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

Solution (Python):
n, k = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = -float('inf')
for i in range(n):
    x = i
    tot = 0
    s = []
    while True:
        x = p[x] - 1
        tot += c[x]
        s.append(c[x])
        if x == i:
            break
    t = 0
    l = len(s)
    for i in range(l):
        t += s[i]
        if i+1 > k:
            break
        now = t
        if tot > 0:
            e = (k-i-1)//l
            now += tot*e
        ans = max(ans, now)
print(ans)

Solution (Python):
from itertools import accumulate


def main():
    cells, moves = [int(x) for x in input().split()]
    jumps_from = [int(x) - 1 for x in input().split()]
    score_on = [int(x) for x in input().split()]

    ans = - 10**10
    for start in range(cells):
        route = []
        route_append = route.append
        position = start
        while True:
            route_append(score_on[position])
            position = jumps_from[position]
            if position == start:  
                break

        length = len(route)
        total = sum(route)
        accum_tmp = 0
        for i, score in enumerate(route):
            accum_tmp += score
            if i + 1 > moves:
                break
            accum = accum_tmp
            if total > 0:
                accum += total * ((moves - (i + 1)) // length)
            ans = max(ans, accum)

        
        
        
        
        
        
        
        
        
    return ans


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

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

ans = -float('inf')
v = [False for _ in range(n)]
for i in range(n):
  j = i
  if v[j]:
    continue
  r = []
  while(v[j] == False):
    r.append(j)
    v[j] = True
    j = p[j]
  cr = []
  for ri in r:
    cr.append(c[ri])
  k1 = k%len(cr)
  k2 = k//len(cr)
  if k2 > 0:
    k1 += len(cr)
    k2 = max(k2-1,0)
  cr2 = cr+cr+cr
  
  now = -float('inf')
  csum = [0 for _ in range(len(cr2)+1)]
  for i0 in range(len(cr2)):
    csum[i0+1] = csum[i0]+cr2[i0]
  for i0 in range(len(cr)):
    for i1 in range(k1):
      now = max(csum[i0+i1+1]-csum[i0],now)
  if sum(cr) > 0:
    now += sum(cr)*k2
  ans = max(ans,now)
print(ans)

Solution (Python):






from itertools import accumulate





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





check = [False]*N
ans = -float("inf")
for i in range(N):
    if not check[i]:
        score = []
        stop = i
        while 1:
            check[i] = True
            score.append(C[i])
            if P[i] == stop:
                break
            i = P[i]
        length = len(score)
        for j in range(length):
            if j != 0:
                score = score[1:] + [score[0]]
            ac = list(accumulate(score))
            if sum(score) <= 0:
                ans = max(ans, max(ac[:min(K,length)]))
            else:
                if K%length == 0:
                    ans = max(ans, ac[-1]*(K//length-1)+max(ac))
                else:
                    ans = max(ans, ac[-1]*(K//length) + max(ac[:K%length]))
print(ans)

Solution (Python):
def main():
 
    N,K = map(int,input().split())
    P = list(map(int,input().split()))
    C = list(map(int,input().split()))
 
    
    import copy
    P2 = set(P)
    Group = []
    while len(P2)>0:
        temp = list(P2)[0]
        tempGroup = []
        while temp in P2:
            tempGroup.append(temp)
            P2.remove(temp)
            temp = P[temp-1]
        Group.append(tempGroup)
    Point = []
    for x in Group:
        tempPoint = []
        for p in x:
            tempPoint.append(C[p-1])
        Point.append(tempPoint)
 
    
    
 
    max00 = -10**9
    for x in Point:
        sumx = sum(x)
        tempx = copy.copy(x)
        tempx.extend(x)
        lenx = len(x)
        max0 = -10**9
        dp = [0]*lenx
        if sumx <= 0 or K < lenx:
            for i in range(min(lenx-1,K)):
                for j in range(lenx):
                    dp[j] = dp[j] + tempx[j+i]
                max0 = max(max0,max(dp))
                
        else:
            K2 = K % lenx
            SN = int(K/lenx)
            for i in range(lenx):
                for j in range(lenx):
                    dp[j] = dp[j] + tempx[j+i]
                
                if i < K2:
                    max0 = max(max0,max(dp) + sumx*SN)
                    
                else:
                    max0 = max(max0,max(dp) + sumx*(SN-1))
        max00 = max(max00,max0)
    print(max00)
 
if __name__ == "__main__":
    main()

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

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






ans = - (10 ** 10)
for start in range(N):
  cur = start
  point_sum = 0
  cnt = 0
  best = []
  while True:
    cur = P[cur] 
    cnt += 1 
    point_sum += C[cur] 
    if len(best) == 0:
      best.append(point_sum)
    else:
      best.append(max(best[-1], point_sum))
    if cur == start:
      break 
  
  
  
  
  
  
  
  
  
  
  
  if point_sum > 0:
    
    loop_count = K // cnt 
    case1_point = loop_count * point_sum
    rest = K % cnt
    if rest > 0:
      case1_point += best[rest - 1]
    
    
    point = case1_point
    
    if loop_count > 0: 
      loop_count -= 1
      case2_point = loop_count * point_sum
      
      case2_point += best[-1]
      
      if point < case2_point:
        point = case2_point
    if ans < point:
      ans = point
  else:
    
    point = 0
    if cnt <= K: 
      point = best[-1]
      
    else:
      
      point = best[cnt - 1]
     
    if ans < point:
      ans = point
  
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()))

S = []
for i in range(N):
    p, si = i, [0]
    ps = set()
    while P[p] not in ps:
        p = P[p]
        ps.add(p)
        si.append(si[-1] + C[p])
    si = si[1:]
    S.append(si)


ans = -float('inf')
for i in range(N):
    for j in range(len(S[i])):
        if K - j - 1 < 0:
            continue

        if S[i][-1] > 0:
            roop = (K - j - 1) // len(S[i])
            ans = max(ans, S[i][-1] * roop + S[i][j])
        else:
            ans = max(ans, S[i][j])

print(ans)

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

score_cnt = [None] * (n + 1)
for i in range(1, n + 1):
    now = i
    cnt = 0
    score = 0
    for _ in range(n):
        now = p[now]
        score += c[now]
        cnt += 1
        if now == i:
            score_cnt[i] = [score, cnt]
            break

ans = - 10 ** 20
for i in range(1, n + 1):
    now = i
    score = 0
    left = k
    for j in range(n):
        now = p[now]
        score += c[now]
        left -= 1
        if left >= 0:
            times = left // score_cnt[now][1]
            score_loop = score + times * score_cnt[now][0]
            ans = max(ans, score, score_loop)

print(ans)

Solution (Python):
N, K = map(int, input().split())
P = list(map(lambda a: int(a) - 1, input().split()))
C = list(map(int, input().split()))
INF = 10**18

grp = []
visited = [False] * N

for i in range(N):
    if visited[i]:
        continue
    V = []
    while not visited[i]:
        V.append(i)
        visited[i] = True
        i = P[i]
    grp.append(V)

def solve(V, K):
    N = len(V)
    sumC = 0
    for v in V:
        sumC += C[v]

    ans = 0
    if sumC > 0 and K >= N:
        q, K = divmod(K, N)
        K += N
        ans = sumC * (q - 1)
    else:
        K = min(K, N)

    if K == 0:
        return ans

    def calc(now):
        acc = C[now]
        ret = acc
        for _ in range(K - 1):
            now = P[now]
            acc += C[now]
            ret = max(ret, acc)
        return ret

    mx = -INF
    for start in V:
        mx = max(mx, calc(start))

    return mx + ans

ans = max(C)
for V in grp:
    ans = max(ans, solve(V, K))
print(ans)

Solution (Python):
N, K = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -float("inf")
for start in range(N):
    x = start
    cyc_score = []
    total_cyc_score = 0
    while True:
        x = P[x]-1
        cyc_score.append(C[x])
        total_cyc_score += C[x]
        if x == start: 
            break
    t = 0
    for i in range(len(cyc_score)):
        t += cyc_score[i]
        if i + 1 > K: break
        now_score = t
        if total_cyc_score > 0:
            e = int((K - i - 1) / len(cyc_score))
            now_score += total_cyc_score * e
        ans = max(ans, now_score)
print(ans)

Solution (Python):
import sys
sys.setrecursionlimit(10**9)

N,K = map(int,input().split())
P = [ i-1 for i in list(map(int,input().split())) ]
C = list(map(int,input().split()))
ans = -float('inf')

for i in range(N):
  cycle = []
  tot = 0
  nex = i
  while True:
    nex = P[nex]
    cycle.append(C[nex])
    tot += C[nex]
    if nex == i: break

  l = len(cycle)
  t = 0
  for j in range(l):
    t += cycle[j]
    if j+1 > K: break
    now = t
    if tot > 0:
      now += tot*((K-(j+1))//l)
    ans = max(ans, now)

print(ans)

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

ans = -10**18

for i in range(n):
    tmp_score = 0
    pos = i
    cycle = 0
    for l in range(k):
        pos = p[pos]-1
        tmp_score += c[pos]
        ans = max(ans,tmp_score)
        cycle += 1
        if pos == i: break
    q,r = divmod(k,cycle)
    if r == 0 and q > 1:
        r = cycle
        q -= 1
    tmp_score *= q
    ans = max(ans,tmp_score)
    for _ in range(r):
        pos = p[pos]-1
        tmp_score += c[pos]
        ans = max(ans,tmp_score)        
print(ans)

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

ans = -10**18

for i in range(n):
    tmp_score = 0
    pos = i
    
    for l in range(k):
        pos = p[pos]-1
        tmp_score += c[pos]
        ans = max(ans,tmp_score)
        
        if pos == i: break
    q,r = divmod(k,l+1)
    if r == 0 and q > 1:
        r = l+1
        q -= 1
    tmp_score *= q
    ans = max(ans,tmp_score)
    for _ in range(r):
        pos = p[pos]-1
        tmp_score += c[pos]
        ans = max(ans,tmp_score)        
print(ans)

Solution (Python):
def res(n):
    pos = n
    cnt = 1
    while 1:
        pos = P[pos]-1
        if pos == n:
            break
        cnt += 1

    tmp = 0
    ans = -float("inf")
    pos = n

    for _ in range(min(K,cnt)):
        pos = P[pos]-1
        tmp += C[pos]
        ans = max(ans,tmp)
    
    
    if tmp > 0 and K > cnt:
        pos = n
        d = K%cnt
        tmp = (K//cnt-1)*tmp
        ans = max(ans,tmp)
        for _ in range(d+cnt):
            pos = P[pos]-1
            tmp += C[pos]
            ans = max(ans,tmp)

    return ans

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):
    ans = max(ans,res(i))

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 = -float('inf')
for st in range(n):
    x = st
    score = []
    tot = 0
    while True:
        x = p[x]
        score.append(c[x])
        tot += c[x]
        if x == st:
            break
    l = len(score)
    now = 0
    t = 0
    for i in range(l):
        t += score[i]
        if i + 1 > k:
            break
        now = t
        if tot > 0:
            cycle_num = (k - (i + 1)) // l
            now += tot * cycle_num
        ans = max(ans, now)
print(ans)

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

P = list(map(int,input().split()))

C = list(map(int,input().split()))

ans = -10000000000

if K <= N:
    for i in range(N):
        count = 0
        tmp_point = 0
        nv = i
        while count < K:
            nvv = P[nv]
            nvv -= 1
            tmp_point += C[nvv]
            count += 1
            nv = nvv
            ans = max(ans, tmp_point)
    print(ans)
else:
    loop = [0]*N
    for i in range(N):
        count = 0
        check = [False]*N
        tmp_point = 0
        nv = i
        while True:
            nvv = P[nv]
            nvv -= 1
            if check[nvv] == True:
                break
            check[nvv] = True
            tmp_point += C[nvv]
            count += 1
            nv = nvv
            ans = max(ans, tmp_point)
        loop[i] = [tmp_point, count, i]
    loop.sort(reverse=True)
    
    new_ans = -10000000
    for value, counter, key in loop:
        if value < 0:
            break
        shou = K//counter-1
        amari = K%counter+counter
        tmp_ans = value*shou
        new_ans = max(new_ans, tmp_ans)
        count = 0
        nv = key
        while count < amari:
            nvv = P[nv]
            nvv -= 1
            tmp_ans += C[nvv]
            count += 1
            nv = nvv
            new_ans = max(new_ans, tmp_ans)

        
    print(max(loop[0][0], ans, new_ans))

Solution (Python):
def main():
    n, k = [int(e) for e in input().split()]
    P = [int(e) for e in input().split()]
    C = [int(e) for e in input().split()]

    A = []
    for i in range(1, n + 1):
        score = 0
        max_score = -(10 ** 18)
        move_count = 0
        di = i
        S = set()
        while True:
            di = P[di - 1]
            if di in S or move_count == k:
                break

            score += C[di - 1]
            if max_score < score:
                max_score = score

            move_count += 1
            S.add(di)

        if score > 0 and move_count < k:
            re = None
            if k % move_count != 0:
                re = k % move_count
                score = score * (k // move_count)
            else:
                re = move_count
                score = score * (k // move_count - 1)

            max_score = score
            di = i
            for si in range(re):
                di = P[di - 1]
                score += C[di - 1]
                if max_score < score:
                    max_score = score

        A.append(max_score)

    print(max(A))


if __name__ == '__main__':
    main()

Solution (Python):
import sys
sys.setrecursionlimit(1000000)

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

    print(ans)


if __name__ == "__main__":
    main()

Solution (Python):

import sys 
from itertools import accumulate
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
N, K = map(int, readline().split())
P = [0] + list(map(int,readline().split()))
C = [0] + list(map(int,readline().split()))

check = [False]*(N+1)
data = []
for i in range(1,N+1):
    if check[i]:
        continue
    cnt = 0
    point = []
    n = i
    while True:
        if check[n]:
            break
        check[n] = True
        cnt += 1
        point.append(C[n])
        n = P[n]
    data.append((cnt,point))

S = len(data)
INF = 10**31
ans = -INF
for i in range(S):
    cnt,point = data[i]
    a = K // cnt
    b = K % cnt
    tt = -INF
    P = [0]+point+point
    SS = list(accumulate(P))
    sum_point = sum(point)
    if a == 0:
        for k in range(1,b+1):
            for i in range(cnt):
                t = SS[i+k]-SS[i]
                tt = max(t,tt)
        tmp = tt
    elif sum_point <= 0:
        for k in range(1,cnt):
                for i in range(cnt):
                    t = SS[i+k]-SS[i]
                    tt = max(t,tt)
        tmp = tt
    else: 
        tmp1 = sum_point * a
        tmp2 = sum_point * (a-1)
        tt1 = 0
        tt2 = 0
        for k in range(1,b+1):
            for i in range(cnt):
                t1 = SS[i+k]-SS[i]
                tt1 = max(t1,tt1)
        tmp1 += tt1

        for k in range(1,cnt):
            for i in range(cnt):
                t2 = SS[i+k]-SS[i]
                tt2 = max(t2,tt2)
        tmp2 += tt2

        tmp = max(tmp1,tmp2)

    ans = max(tmp,ans)
print(ans)

Solution (Python):
def cin():  return list(map(int,input().split()))

N, K = cin()
P = cin()
C = cin()
for i in range(N):  P[i] -= 1

ans = -(10 ** 9 + 7)

for i in range(N):
    c = []
    j = i
    
    while(P[j] != i):
        j = P[j]
        c.append(C[j])
    c.append(C[i])
    
    if sum(c) <= 0:
        acc = [0]
        for i in c:  acc.append(acc[-1] + i)
        ans = max(ans, max(acc[1:K + 1]))
        
    else:
        loop_cnt = K // len(c)
        loop_mod = K - len(c) * loop_cnt
        acc = [(loop_cnt - 1) * sum(c)]
        for i in c:  acc.append(acc[-1] + i)
        for i in range(loop_mod):  acc.append(acc[-1] + c[i])
        ans = max(ans, max(acc))
        
print(ans)

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




ans = -(10**9)

for i in range(1, N + 1):
    
    route = []
    visit = [False] * (N + 1)
    visit[i] = True
    now = i
    while True:
        next = P[now]
        
        if visit[next] == False:
            visit[next] = True
            route.append(next)
            now = next
        
        else:
            break
    
    route.append(i)

    cumsum = [0]
    for x in route:
        cumsum.append(cumsum[-1] + C[x])
    

    
    if cumsum[-1] <= 0:
        if K >= len(route):
            tmp = max(cumsum[1:])
        else:
            tmp = max(cumsum[1:K + 1])
        ans = max(ans, tmp)
    
    else:
        loop_size = len(route)
        loop_cnt = K // loop_size
        spare_cnt = K % loop_size
        
        cumsum2 = [cumsum[-1] * (loop_cnt - 1)]
        for x in route:
            cumsum2.append(cumsum2[-1] + C[x])
        for x in route[:spare_cnt]:
            cumsum2.append(cumsum2[-1] + C[x])
        tmp = max(cumsum2[1:])
        ans = max(ans, tmp)

print(ans)

Solution (Python):


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

    ans = -10**9 - 1

    for si in range(N):
        g = []
        tot = 0
        cur = si
        while True:
            cur = P[cur]
            g.append(C[cur])
            tot += C[cur]
            if cur == si or len(g) == K:
                break

        L = len(g)
        t = 0
        for i, x in enumerate(g, start=1):
            t += x
            now = t
            if tot > 0:
                rep = (K - i) // L
                now += tot * rep

            ans = max(ans, now)

    print(ans)


if __name__ == '__main__':
    main()

Solution (Python):
n,k=[int(i) for i in raw_input().split()]
p=[int(i)-1 for i in raw_input().split()]
c=[int(i) for i in raw_input().split()]
maxx=-10**18
for i in range(n):
  ct=0;j=0;pos=i
  v=[0]*n
  arr=[]
  while j<k:
    if(v[pos]==1):
  	    break
    v[pos]=1
    ct+=c[pos]
    pos=p[pos]
    arr.append(ct)
    j+=1
  val=0
  if(ct>0):
  	val=ct*((k-j)/j)
  else:
  	val=0
  k1=k
  k1%=j
  k1+=j
  for i1 in range(len(arr)):
  	if(k1-i1>j):
  	    maxx=max(maxx,val+arr[i1],val+ct+arr[i1])
  	else:
  	    maxx=max(maxx,val+arr[i1])
print maxx

Solution (Python):
import itertools as it

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

N, K = li()
P = [0] + li()
C = [0] + li()

def get_cycle(start_i):
    cycle = []
    i = start_i
    while True:
        i = P[i]
        if i == start_i:
            break
        cycle.append(i)
    cycle.append(start_i)
    return cycle

max_scores = []
for start_i in range(1,N+1):
    cycle = get_cycle(start_i)
    
    scores = list(it.accumulate([0]+[C[i] for i in cycle]))
    cycle_len = len(cycle)
    score_per_cycle = scores[cycle_len]
    
    if K <= len(cycle):
        max_score = max(scores[1:K+1])
        max_scores.append(max_score)
        continue
    
    if score_per_cycle <= 0:
        max_score = max(scores[1:])
        max_scores.append(max_score)
        continue
    
    
    scores_last_cycle = []
    for move in range(K-cycle_len+1, K+1):
        
        loop_cnt = move // cycle_len
        
        rest_move = move % cycle_len
        
        score = loop_cnt * score_per_cycle + scores[rest_move]
        scores_last_cycle.append(score)

    max_scores.append(max(scores_last_cycle))

print(max(max_scores))

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




def junkan(N):
  
  masu=[0]*(n+1)
  ans=0
  ans22=-(10**9+1)
  junkan_flag=False
  now_mas=p[N-1]
  count=0
  masu[now_mas]=1
  
  while True:
    if count>=k:
      break
    if (count!=0 and masu[now_mas]==1):
      junkan_flag=True
      break
    count+=1
    ans+=c[now_mas-1]
    
    if ans22<ans:
      ans22=ans
      
    masu[now_mas]=1
    now_mas=p[now_mas-1]
  if junkan_flag==True and ans>0:
    ans=(((k-1)//count)-1)*ans
    
    if ans22<ans:
      ans22=ans
    for i in range(k-((k-1)//count-1)*count):
      ans+=c[now_mas-1]
      if ans22<ans:
        ans22=ans
        
      now_mas=p[now_mas-1]
    return max(ans,ans22)
  
  else:
    return max(ans,ans22)
answ=-(10**9+1)

for i in range(1,n+1):
  hantei=junkan(i)
  if answ < hantei:
    answ=hantei
print(answ)

Solution (Python):
import math

def split_to_loops(G):
    
    
    
    
    
    

    loops = []
    _all = set(range(len(G)))

    while _all:
        s = _all.pop()
        loop = [s]
        v = G[s]
        while v != s:
            _all.remove(v)
            loop.append(v)
            v = G[v]

        loops.append(loop)

    return loops

def find_max_continued(A, n):
    
    
    
    
    
    
    
    
    

    
    _max = max(A)

    
    L = len(A)
    for d in range(2, min(n+1, L+1)):
        _sum = sum(A[:d])
        _max = max(_max, _sum)
        
        for i in range(d, L):
            _sum += A[i] - A[i-d]
            _max = max(_max, _sum)
        for i in range(d):
            _sum += A[i] - A[L-d+i]
            _max = max(_max, _sum)

    return _max

def find_max_in_one_loop(loop, K, C):
    
    L = len(loop)
    loop_c = [C[v] for v in loop] 

    
    sum_1_loop = sum(loop_c)
    

    if sum_1_loop < 0:
        
        return find_max_continued(loop_c, min(K, L))
    else:
        
        if K < L:
            return find_max_continued(loop_c, K)

        
        

        n_loops = K // L 

        
        
        
        n_loops -= 1
        
        score = sum_1_loop * n_loops
        K -= n_loops * L 

        
        score_no_loop = find_max_continued(loop_c, L)
        
        
        score_loop = sum_1_loop
        if K != L:
            
            score_loop += find_max_continued(loop_c, K - L)
        
        score += max(score_no_loop, score_loop)
        return score

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

    
    
    
    
    
    loops = split_to_loops(P)
    

    ans = -(10 ** 10)
    for loop in loops:
        
        
        ans = max(ans, find_max_in_one_loop(loop, K, C))
    
    print(ans)

if __name__ == '__main__':
    main()