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 sys;      from decimal import Decimal
import math;     from itertools import combinations, product, accumulate
import bisect;   from collections import Counter, deque, defaultdict


MOD = 10 ** 6 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

def Main():
    n, k = read_ints()
    p = read_int_list()
    c = read_int_list()
    loop_list = []
    visit = [False] * n

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

        visit[i] = True
        now = i
        loop_tmp = []

        while True:
            now = p[now] - 1
            visit[now] = True
            loop_tmp.append(c[now])
            if visit[p[now] - 1]:
                loop_tmp.append(c[p[now] - 1])
                break
        loop_list.append(loop_tmp)

    
    ans = -10 ** 18

    
    for loop in loop_list:
        length = len(loop)
        score = sum(loop)
        if k > length:
            if score > 0:
                ans = max(ans, (k // length) * score + search_max_score(loop, k % length, length), (k // length - 1) * score + search_max_score(loop, length, length))
            else:
                ans = max(ans, search_max_score(loop, length, length))
        else:
            ans = max(ans, search_max_score(loop, k, length))
    
    print(ans)


def search_max_score(loop, rest, length):
    if rest == 0:
        ans = 0
    elif rest == 1:
        ans = max(loop)
    else:
        ans = -10**18
        loop += loop
        for i in range(length):
            tmp = list(accumulate(loop[i:i + rest]))
            
            ans = max(ans, max(tmp))
    
    return ans

if __name__ ==  '__main__':
    Main()

Solution (Python):
N, K = [int(i) for i in input().split()]
P = [int(i)-1 for i in input().split()]
C = [int(i) for i in input().split()]
def f(s):
    tmp = s
    circle_length = 0
    circle_score = 0
    for i in range(1, N+1):
        tmp = P[tmp]
        circle_length += 1
        circle_score += C[tmp]
        if s == tmp:
            return (True, circle_length, circle_score)
        if i == K:
            return (False, K, -10**10)

def f1(s, circle_length):
    tmp = s
    max_score = -10**10
    tmp_score = 0
    for i in range(1, circle_length+1):
        tmp = P[tmp]
        tmp_score += C[tmp]
        if max_score < tmp_score:
            max_score = tmp_score
        if tmp_score < 0:
            return max_score
        if i == K:
            return max_score
    return max_score

def f2(s, circle_length, circle_score):
    max_score = (K//circle_length) * circle_score
    tmp = s
    tmp_score = 0
    for i in range(1, (circle_length)+1):
        tmp = P[tmp]
        tmp_score += C[tmp]
        score = ((K-i)//circle_length) * circle_score + tmp_score
        if max_score < score:
            max_score = score
        if tmp_score < 0:
            return max_score
        if i == K:
            return max_score
    return max_score

tot_max = -10**10
for i in range(N):
    is_circle, circle_length, circle_score = f(i)
    max_score = f1(i, circle_length)
    if is_circle and circle_score > 0:
        max_score2 = f2(i, circle_length, circle_score)
        if max_score2 > max_score:
            max_score = max_score2
    if max_score > tot_max:
        tot_max = max_score
print(tot_max)

Solution (Python):




import sys;      from decimal import Decimal
import math;     from itertools import combinations, product, accumulate
import bisect;   from collections import Counter, deque, defaultdict


MOD = 10 ** 6 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def lcm(a: int, b: int) -> int: return (a * b) // math.gcd(a, b)

def Main():
    n, k = read_ints()
    p = read_int_list()
    c = read_int_list()
    loop_list = []
    visit = [False] * n

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

        visit[i] = True
        now = i
        loop_tmp = []

        while True:
            now = p[now] - 1
            visit[now] = True
            loop_tmp.append(c[now])
            if visit[p[now] - 1]:
                loop_tmp.append(c[p[now] - 1])
                break
        loop_list.append(loop_tmp)

    
    ans = -10 ** 18

    
    for loop in loop_list:
        length = len(loop)
        score = sum(loop)
        if k > length:
            if score > 0:
                ans = max(ans, (k // length) * score + search_max_score(loop, k % length, length), (k // length - 1) * score + search_max_score(loop, length, length))
            else:
                ans = max(ans, search_max_score(loop, length, length))
        else:
            ans = max(ans, search_max_score(loop, k, length))
    
    print(ans)


def search_max_score(loop, rest, length):
    if rest == 0:
        ans = 0
    elif rest == 1:
        ans = max(loop)
    else:
        ans = -10**18
        loop += loop
        for i in range(length):
            tmp = list(accumulate(loop[i:i + rest]))
            
            ans = max(ans, max(tmp))
    
    return ans

if __name__ ==  '__main__':
    Main()

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()))
ans = max(C)
for i in range(N):
    p = i
    d = []
    while True:
        p = P[p]
        d.append(C[p])
        if p == i:
            break
    
    val = 0
    for j in range(min(K,len(d))):
        val += d[j]
        ans = max(ans,val)
        



    if K > len(d):
        k = K % len(d)
        val = (K//len(d)) * sum(d)
        ans = max(ans,val)
        for j in range(k):
            val += d[j]
            ans = max(ans,val)

        val = (K//len(d)-1) * sum(d)
        for j in range(len(d)):
            val += d[j]
            ans = max(ans,val)

print(ans)

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


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


ans = -10**20
se = set()
for start in range(N):
    if start in se:
        continue
    now = start
    scores = []
    while True:
        if now in se:
            break
        se.add(now)
        scores += [C[now]]
        now = P[now]
    cyclelen = len(scores)
    cum = list(itertools.accumulate(scores * 3))
    st = SegmentTree(cum, max, -10**20)
    cycle, residue = divmod(K, cyclelen)
    ans = max([ans] + [
        st.query(start2 + 1, start2 + 1 + min(cyclelen, K)) - cum[start2]
        for start2 in range(cyclelen)
    ])
    if cum[-1] > 0 and cycle > 0:
        v = cum[-1] * cycle // 3 + max(
            st.query(0, start2 + residue + 1) - cum[start2]
            for start2 in range(cyclelen, 2 * cyclelen))
        ans = max(ans, v)
print(ans)

Solution (Python):




if __name__ == "__main__":

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

	

	ans = -1e10

	for n in range(N):

		v = n
		currentCycleItemCnt = 0
		currentCycleTotal = 0

		while True:
			
			currentCycleItemCnt += 1
			currentCycleTotal += C[v]

			v = P[v]
			if v == n:
				
				break

		procCnt = 0
		currentCycleSumTmp = 0

		while True:

			
			
			procCnt += 1
			currentCycleSumTmp += C[v]
			if K < procCnt:
				break

			cycleLoopCnt = 0
			if procCnt < K and 0 < currentCycleTotal:
				cycleLoopCnt = ( K - procCnt ) // currentCycleItemCnt

			
			tmp = currentCycleSumTmp + cycleLoopCnt * currentCycleTotal
			ans = max( ans, tmp )

			v = P[v]
			if v == n:
				
				break

	print(ans)

Solution (Python):




if __name__ == "__main__":

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

	
	
	cycleIDs = [ -1 for _ in range(N) ]
	cycleInfs = []


	

	ans = -1e10
	cycleID = 0

	for n in range(N):

		v = n
		currentCycleItemCnt = 0
		currentCycleTotal = 0

		if cycleIDs[v] != -1:
			currentCycleItemCnt, currentCycleTotal = cycleInfs[ cycleIDs[v] ]
			
		else:
			while True:
				
				currentCycleItemCnt += 1
				currentCycleTotal += C[v]

				v = P[v]
				if v == n:
					
					cycleInfs.append( (currentCycleItemCnt, currentCycleTotal) )
					cycleID += 1
					break

				
				
				cycleIDs[v] = cycleID

		procCnt = 0
		currentCycleSumTmp = 0

		while True:

			
			
			procCnt += 1
			currentCycleSumTmp += C[v]
			if K < procCnt:
				break

			cycleLoopCnt = 0
			if procCnt < K and 0 < currentCycleTotal:
				cycleLoopCnt = ( K - procCnt ) // currentCycleItemCnt

			
			tmp = currentCycleSumTmp + cycleLoopCnt * currentCycleTotal
			ans = max( ans, tmp )

			v = P[v]
			if v == n:
				
				break

	print(ans)

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


class SegmentTree():
    def __init__(self, array, f, ti):
        """
        Parameters
        ----------
        array : list
            to construct segment tree from
        f : func
            binary operation of the monoid
        ti : 
            identity element of the monoid
        """
        self.f = f
        self.ti = ti
        self.n = n = 2**(len(array).bit_length())
        self.dat = dat = [ti] * n + array + [ti] * (n - len(array))
        for i in range(n - 1, 0, -1):  
            dat[i] = f(dat[i << 1], dat[i << 1 | 1])

    def update(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = v
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_right(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(dat[p], v)
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def operate_left(self, p, v):  
        f, n, dat = self.f, self.n, self.dat
        p += n
        dat[p] = f(v, dat[p])
        while p > 1:
            p >>= 1
            dat[p] = f(dat[p << 1], dat[p << 1 | 1])

    def query(self, l, r):  
        f, ti, n, dat = self.f, self.ti, self.n, self.dat
        vl = vr = ti
        l += n
        r += n
        while l < r:
            if l & 1:
                vl = f(vl, dat[l])
                l += 1
            if r & 1:
                r -= 1
                vr = f(dat[r], vr)
            l >>= 1
            r >>= 1
        return f(vl, vr)


ans = -10**20
se = set()
for start in range(N):
    if start in se:
        continue
    now = start
    scores = []
    while True:
        if now in se:
            break
        se.add(now)
        scores += [C[now]]
        now = P[now]
    cyclelen = len(scores)
    cum = list(itertools.accumulate(scores * 2))
    st = SegmentTree(cum, max, -10**20)
    cycle, residue = divmod(K, cyclelen)
    ans = max([ans] + [
        st.query(start2 + 1, start2 + 1 + min(cyclelen, K)) - cum[start2]
        for start2 in range(cyclelen)
    ])
    if cum[-1] > 0 and cycle > 0:
        v1 = cum[-1] * (cycle - 1) // 2 + max(
            st.query(start2, start2 + cyclelen + 1) - cum[start2]
            for start2 in range(cyclelen))
        v2 = cum[-1] * cycle // 2 + max(
            st.query(start2, start2 + residue + 1) - cum[start2]
            for start2 in range(cyclelen))
        ans = max([ans, v1, v2])
print(ans)

Solution (Python):
n,k=map(int,input().split())
p=list(map(int,input().split()))
c=list(map(int,input().split()))
root=[]
mi=set(range(n))
while mi:
  v=mi.pop()
  r=[c[v]]
  while p[v]-1 in mi:
    r.append(c[p[v]-1])
    mi.discard(p[v]-1)
    v=p[v]-1
  root.append(r)
inf=float('inf')
ans=-inf
for r in root:
  ansr=-inf
  k1=k%len(r)
  k0=k//len(r)
  cr=[0]
  tmp=0
  for ri in r:
    tmp+=ri
    cr.append(tmp)
  sumr=cr[-1]
  for ri in r:
    tmp+=ri
    cr.append(tmp)
  for i in range(len(r)):
    for j in range(i,i+min(k,len(r))):
      ansr=max(ansr,cr[j+1]-cr[i])
  if sumr>0:
    ans=max(ans,ansr+sumr*(k0-1))
  else:
    ans=max(ans,ansr)
  if sumr>0:
    ansr=0
    for i in range(len(r)):
      for j in range(i,i+k1):
        ansr=max(ansr,cr[j+1]-cr[i])    
    ans=max(ans,ansr+sumr*k0)
print(ans)

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

P = [None] + P
C = [None] + C

all_max = C[1]
for st in range(1, N + 1):
    scores = []
    visit = set()
    p = st

    while p not in visit and len(visit) < K:
        next_p = P[p]
        scores.append(C[next_p])
        visit.add(p)
        p = next_p

    num_elem = len(scores)
    all_sum = sum(scores)

    q, r = divmod(K, num_elem)

    max_ = scores[0]
    temp = scores[0]

    max_r = scores[0]
    temp_r = scores[0]
    for x in range(1, num_elem):
        if x < r:
            temp_r += scores[x]
            max_r = max(max_r, temp_r)

        temp += scores[x]
        max_ = max(max_, temp)

    temp_max = scores[0]
    if all_sum > 0 and q > 0:
        if r > 0:
            temp_max = max(all_sum * (q - 1) + max_, all_sum * q + max_r)
        else:
            temp_max = all_sum * (q - 1) + max_
    else:
        temp_max = max_

    all_max = max(all_max, temp_max)


print(all_max)

Solution (Python):
n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

INF = 10**18
score = -INF
for st in range(n):
    lap_cn = 0
    lap_sc = 0
    nx = st
    while True:
        lap_cn += 1
        lap_sc += C[nx]
        nx = P[nx]
        if nx == st: break
    lap_sc = max(0, lap_sc)

    sum_sc = 0
    k_cn = 0
    while True:
        k_cn += 1
        if k < k_cn: break
        sum_sc += C[nx]
        score = max(score, sum_sc + lap_sc * ((k - k_cn) // lap_cn))
        nx = P[nx]
        if nx == st: break

print(score)

Solution (Python):



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

rc = [0] * n
rp = [0] * n
for i in range(n):
    if rc[i]!=0:
        continue
    else:
        nw = set([i])
        np = c[i]
        nx = p[i]
        while not nx in nw:
            nw.add(nx)
            np += c[nx]
            nx = p[nx]
        cnt = len(nw)
        for x in nw:
            rc[x] = cnt
            rp[x] = np
ret = - 10 ** 18
for i in range(n):
    if rc[i] == 1:
        if rp[i]>=0:
            ret = max(ret, k*rp[i])
        else:
            ret = max(ret, rp[i])
        continue
    pseq = [0]
    nx = p[i]
    for j in range(1,rc[i]+1):
        pseq.append(pseq[-1]+c[nx])
        nx = p[nx]
    pseq = pseq[1:]
    if k <= rc[i]:
        ret = max(ret, max(pseq[:k]))
    elif rp[i] < 0:
        ret = max(ret, max(pseq))
    else:
        tmp = max(pseq)
        if k%rc[i]!=0:
            tmp = max(tmp, rp[i] + max(pseq[:k%rc[i]]))
        tmp += rp[i]*(k//rc[i]-1)
        ret = max(ret, tmp)
print(ret)

Solution (Python):



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

ret = - 10 ** 18
for s in range(n):
    nxt = p[s]
    S = [c[nxt]]
    while nxt != s:
        nxt = p[nxt]
        S.append(S[-1]+c[nxt])

    if k<=len(S):
        pt = max(S[:k])
    else:
        if S[-1] <= 0:
            pt = max(S)
        else:
            pt = max(S)
            if k%len(S)!=0:
                pt = max(pt, S[-1]+max(S[:k%len(S)]))
            pt += S[-1]*(k//len(S)-1)
    ret = max(ret, pt)
print(ret)

Solution (Python):
n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

INF = 10**18
max_score = -INF
for st in range(n):
    lc = 0 
    lap_sc = 0 
    nx = st
    while True:
        lc += 1
        lap_sc += C[nx]
        nx = P[nx]
        if nx == st: break

    lap_sc = max(0, lap_sc)
    sum_sc = 0
    kc = 0
    while True:
        kc += 1
        if k < kc: break
        sum_sc += C[nx]
        score = sum_sc + lap_sc * ((k - kc) // lc)
        max_score = max(max_score, score)
        nx = P[nx]
        if nx == st: break

print(max_score)

Solution (Python):
n, k = map(int, input().split())
P = [*map(lambda x: int(x)-1, input().split())]
C = [*map(int, input().split())]

INF = 10**18
max_score = -INF
for st in range(n):
    lc = 0 
    lap_sc = 0 
    nx = st
    while True:
        lc += 1
        lap_sc += C[nx]
        nx = P[nx]
        if nx == st: break

    sum_sc = 0
    kc = 0
    while True:
        kc += 1
        if k < kc: break

        sum_sc += C[nx]
        score = sum_sc + max(0, lap_sc) * ((k - kc) // lc)
        max_score = max(max_score, score)

        nx = P[nx]
        if nx == st: break

print(max_score)

Solution (Python):
N,K=map(int,input().split())
P=[0]+list(map(int,input().split()))
C=[0]+list(map(int,input().split()))
D=[0 for i in range(N+1)]
D[0]=5

ans=-10**20
for i in range(1,N+1):
    if D[i]==0:
        D[i]=1
        p=P[i]
        cnt=-10**20
        L=[0]
        l=[i]
        for j in range(10**7):
            if D[p]==5:
                break
            else:
                D[p]+=1
                L.append(L[-1]+C[p])
                l.append(p)
                p=P[p]
        
        
        loop_len=len(L)//5
        loop_cnt=L[loop_len]
        
        
        R=K//loop_len
        M=K%loop_len
        loop_max=-10**20
        if R>=2 and loop_cnt>0:
            cnt+=(R-2)*loop_cnt
            for x in range(loop_len):
                for y in range(1,M+2*loop_len+1):
                    loop_max=max(loop_max,L[y+x]-L[x])
            cnt=max(cnt,loop_cnt*(R-2)+loop_max)
            
            ans=max(ans,cnt)
        else:
            cnt=-10**20
            for x in range(loop_len):
                for y in range(1,min(K,2*loop_len)+1):
                    cnt=max(cnt,L[y+x]-L[x])
                    
            ans=max(ans,cnt)

print(ans)

Solution (Python):





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





fresh = [False] + [True] * N 






def search_loop(start):
    log = [start] 
    last  = start 
    score = [C[start-1]]
    counter = 0
    while True:
        next_spot = P[last - 1]
        counter += 1
        
        if(fresh[next_spot]):
            
            log.append(next_spot)
            score.append(C[next_spot-1])
            last = next_spot
            fresh[next_spot] = False
            
        else:
            
            last = next_spot
            fresh[next_spot] = False
            
            break
    del log[-1]
    del score[-1]
    
    return log, counter-1, sum(score), score
    

status = True
list_loop = []
list_elements = []
list_sum = []
list_score = []

while status:
    for i in range(N+1):
        if(fresh[i]):
            
            a = search_loop(i)
            list_loop.append(a[0])
            list_elements.append(a[1])
            list_sum.append(a[2])
            list_score.append(a[3])
            break
        if(i == N):
            status = False

      




'''
def count_sum(score,elements,start,goal):
    
    if(start==goal):
        return 0, 0
    elif(goal > start):
        
        
        return goal-start, sum(score[start+1:goal+1])
    else:
        l = score + score
        
        
        return goal+elements-start, sum(l[start+1:goal+elements+1])
'''




def zentansaku(loop, elements, sum, score):
    
    
    best = (-1)*(10**10)
    for start in range(elements):
        
        now = 0
        for step in range(elements):
            
            
            
            '''
            if(start != goal):
                step += 1
                now += score[goal]
            '''
            if(step > 0):
                now += score[(step+start)%elements]
            
            if(step > K):
                
                result = (-1)*(10**10)
            else:
                if(sum > 0):
                    
                    available_looping = (K-step) // elements
                    
                    result = sum * available_looping + now
                else:
                    if(step > 0):
                        result = now
                    else:
                        result = (-1)*(10**10)
            best = max(result, best)
            
            
            
    return best
            


ans = (-1)*(10**10)
for i in range(len(list_elements)):
    
    ans = max(ans, zentansaku(list_loop[i], list_elements[i], list_sum[i], list_score[i]))
    
    

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()))
ans = max(C)
for i in range(N):
    p = i
    d = []
    while True:
        p = P[p]
        d.append(C[p])
        if p == i:
            break
    
    val = 0
    for j in range(min(K,len(d))):
        val += d[j]
        ans = max(ans,val)
        
    if K > len(d):
        val = val = (K//len(d)-1) * sum(d)
        k = K - (K//len(d)-1)*len(d)
        d += d
        ans = max(ans,val)
        for j in range(min(k,len(d))):
            val += d[j]
            ans = max(ans,val)


print(ans)

Solution (Python):
def examA():
    S = SI()
    ans = 0
    if "R" in S:
        ans = 1
    if "RR" in S:
        ans = 2
    if "RRR" in S:
        ans = 3
    print(ans)
    return

def examB():
    N = I()
    L = LI()
    L.sort()
    cnt = 0
    for i in range(N):
        for j in range(i+1,N):
            for k in range(j+1,N):
                if L[i]==L[j]:
                    continue
                if L[j]==L[k]:
                    continue
                if L[i]+L[j]>L[k]:
                    cnt += 1
    ans = cnt
    print(ans)
    return

def examC():
    X, K, D = LI()
    if X<0:
        X = -X
    ans = inf
    if X>K*D:
        ans = X-K*D
        print(ans)
        return

    K -= X//D
    X -= D * (X//D)

    ans = X
    if K>0:
        if K%2==1:
            ans = abs(X-D)
    print(ans)
    return


def examD():
    N, K = LI()
    P = LI()
    C = LI()

    B = [i for i in range(N)]
    for i, p in enumerate(P):
        p -= 1
        B[i] = p

    locat_doubling = [[0] * N for _ in range(31)]
    score_doubling = [[0] * N for _ in range(31)]

    for i in range(N):
        locat_doubling[0][i] = i
        locat_doubling[1][B[i]] = i
        score_doubling[0][i] = 0
        score_doubling[1][B[i]] = C[i]
    for k in range(2, 31):
        for i in range(N):
            locat_doubling[k][i] = locat_doubling[k - 1][locat_doubling[k - 1][i]]
            score_doubling[k][i] = score_doubling[k - 1][i] + score_doubling[k - 1][locat_doubling[k - 1][i]]

    score = [[-inf for i in range(31)] for _ in range(N)]
    locate = [[i, i] for i in range(N)]
    ans = max(C)
    for i in range(N):
        score[i][0] = 0

    if ans <= 0:
        print(ans)
        return

    for k in range(30)[::-1]:
        for i in range(N):
            if score[i][k] < 0:
                continue
            
            if score_doubling[k + 1][locate[i][1]] > 0:
                score[i][1] += score_doubling[k + 1][locate[i][1]]
                locate[i][1] = locat_doubling[k + 1][locate[i][1]]

        if K & (1 << k) > 0:
            for i in range(N):
                if score[i][k] < score[i][0]:
                    score[i][k] = score[i][0]
                    locate[i][k] = locate[i][0]
                score[i][0] += score_doubling[k + 1][locate[i][0]]
                locate[i][0] = locat_doubling[k + 1][locate[i][0]]

    for s in score:
        ans = max(ans, s[0], s[1])
    print(ans)
    return

def examD2():
    N, K = LI()
    P = LI()
    C = LI()
    checked = [False]*N
    cycle = [[0]*2 for _ in range(N)]

    ans = max(C)
    if ans<=0:
        print(ans)
        return

    for i in range(N):
        if checked[i]:
            continue
        used = [False]*N
        v = i
        cnt = 0
        score = 0
        cycle_use = set()

        while(not used[v]):
            used[v] = True
            cnt += 1
            score += C[v]
            cycle_use.add(v)
            v = P[v]-1

        for i in cycle_use:
            cycle[i] = [cnt, score]
            checked[i] = True

    for i in range(N):
        c,s = cycle[i]
        cur = s * ((K - c) // c)
        if s<0:
            cur = 0
        rest = K - c * ((K-c)//c)
        if ans<cur:
            ans = cur
        now = i
        for _ in range(rest):
            cur += C[now]
            now = P[now] - 1
            if ans<cur:
                ans = cur

    print(ans)
    return

def examE():
    R, C, K = LI()
    V = [[-inf]*C for _ in range(R)]
    for _ in range(K):
        r,c,v = LI()
        V[r-1][c-1] = v
    dp0 = [[0]*(C+1) for _ in range(R+1)]
    dp1 = [[0]*(C+1) for _ in range(R+1)]
    dp2 = [[0]*(C+1) for _ in range(R+1)]
    dp3 = [[0]*(C+1) for _ in range(R+1)]

    for r in range(R):
        for c in range(C):
            v = V[r][c]
            if 0<v:
                dp0[r+1][c+1] = max(dp0[r+1][c],dp0[r][c+1],dp1[r][c+1],dp2[r][c+1],dp3[r][c+1])
                dp1[r+1][c+1] = max(dp1[r+1][c],dp0[r+1][c]+v,dp0[r][c+1]+v,dp1[r][c+1]+v,dp2[r][c+1]+v,dp3[r][c+1]+v)
                dp2[r+1][c+1] = max(dp2[r+1][c],dp1[r+1][c]+v)
                dp3[r+1][c+1] = max(dp3[r+1][c],dp2[r+1][c]+v)
            else:
                dp0[r+1][c+1] = max(dp0[r+1][c],dp0[r][c+1],dp1[r][c+1],dp2[r][c+1],dp3[r][c+1])
                dp1[r+1][c+1] = dp1[r+1][c]
                dp2[r+1][c+1] = dp2[r+1][c]
                dp3[r+1][c+1] = dp3[r+1][c]

    ans = max(dp0[R][C],dp1[R][C],dp2[R][C],dp3[R][C])
    print(ans)
    return

def examF():
    N = I()
    S = ["" for _ in range(N)]
    C = [0 for _ in range(N)]
    for i in range(N):
        s, c = LSI()
        S[i] = s
        C[i] = c

    ans = 0
    print(ans)
    return

from decimal import getcontext,Decimal as dec
import sys,bisect,itertools,heapq,math,random
from copy import deepcopy
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
def I(): return int(input())
def LI(): return list(map(int,sys.stdin.readline().split()))
def DI(): return dec(input())
def LDI(): return list(map(dec,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet,_ep
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
_ep = dec("0.000000000001")
alphabet = [chr(ord('a') + i) for i in range(26)]
alphabet_convert = {chr(ord('a') + i): i for i in range(26)}

getcontext().prec = 28

sys.setrecursionlimit(10**7)

if __name__ == '__main__':
    examD2()

"""
142
12 9 1445 0 1
asd dfg hj o o
aidn
"""