AtCoder Beginner Contest 175 - Moving Piece

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-----
5 2
2 4 5 1 3
3 4 -10 -8 8

-----Sample Output-----
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.

Difficulty: MEDIUM

Starter code:

Solutions:
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
maximum = -10 ** 9
for i in range(n):
	totalfull = 0
	totalcut = 0
	count = 0
	location = i
	maximumfull = -10 ** 9
	maximumcut = -10 ** 9
	for j in range(min(n, k)):
		location = p[location] - 1
		totalfull += c[location]
		maximumfull = max(maximumfull, totalfull)
		count += 1
		if location == i:
			break
	for j in range(k % count):
		location = p[location] - 1
		totalcut += c[location]
		maximumcut = max(maximumcut, totalcut)
	maximum = max(maximum, max(maximumfull, max((k // count - 1) * totalfull + maximumfull, k // count * totalfull + maximumcut)))
print(maximum)


(n, k) = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
c = list(map(int, input().split()))
s = [0] * (n + 1)
ans = -float('inf')
for i in range(n):
	x = i
	tmp = [-10 ** 9] * (n + 1)
	for j in range(1, n + 1):
		s[j] = s[j - 1] + c[p[x]]
		tmp[j] = max(tmp[j - 1], s[j])
		x = p[x]
		if x == i:
			break
	if j >= k:
		ans = max(ans, tmp[k])
	elif s[j] < 0:
		ans = max(ans, tmp[j])
	else:
		m = k // j
		a = s[j] * (m - 1) + tmp[j]
		b = s[j] * m + tmp[k % j]
		ans = max(ans, a, b)
print(ans)


(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = -float('inf')
for start in range(N):
	loop_len = 1
	pos = P[start]
	score = C[pos]
	scores = [score]
	while pos != start:
		loop_len += 1
		pos = P[pos]
		score += C[pos]
		scores.append(score)
	loops = (K - 1) // loop_len
	if score > 0:
		cand = max(0, score * loops) + max(scores[:K - loop_len * loops])
	else:
		cand = max(scores[:min(K, loop_len)])
	ans = max(ans, cand)
print(ans)


(n, k) = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
c = list(map(int, input().split()))
ans = max(c)
for i in range(n):
	curr = 0
	score = [0]
	posi = i
	while p[posi] != i:
		posi = p[posi]
		curr += c[posi]
		score.append(curr)
	cycle_score = score[-1] + c[i]
	cycle_len = len(score)
	for j in range(cycle_len):
		if j <= k and j != 0:
			cycles = (k - j) // cycle_len
			thing = score[j] + max(0, cycle_score) * cycles
			ans = max(ans, thing)
		elif j == 0 and k >= cycle_len:
			thing = cycle_score * k // cycle_len
			ans = max(ans, thing)
print(ans)


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()
	c = [0] * n
	for i in range(n):
		p[i] -= 1
		c[i] = _c[p[i]]
	m = 31
	MIN = -(1 << 63)
	vertex = list()
	score = list()
	vertex.append(p)
	score.append(c)
	for a in range(1, m + 1):
		p_ath = [0] * n
		c_ath = [0] * n
		for i in range(n):
			p_ath[i] = vertex[a - 1][vertex[a - 1][i]]
			c_ath[i] = score[a - 1][i] + score[a - 1][vertex[a - 1][i]]
		vertex.append(p_ath)
		score.append(c_ath)
	prv = [[MIN, 0] for _ in range(n)]
	nxt = [[MIN, MIN] for _ in range(n)]
	for b in range(m, -1, -1):
		for i in range(n):
			if k >> b & 1:
				nxt[vertex[b][i]][0] = max(nxt[vertex[b][i]][0], prv[i][0] + score[b][i])
				nxt[vertex[b][i]][1] = max(nxt[vertex[b][i]][1], prv[i][1] + score[b][i])
				nxt[i][0] = max(nxt[i][0], prv[i][0], prv[i][1])
			else:
				nxt[vertex[b][i]][0] = max(nxt[vertex[b][i]][0], prv[i][0] + score[b][i])
				nxt[i][0] = max(nxt[i][0], prv[i][0])
				nxt[i][1] = max(nxt[i][1], prv[i][1])
		(prv, nxt) = (nxt, prv)
	ans = max((max(x) for x in prv))
	if ans == 0:
		ans = max(c)
	print(ans)
	return
solve()


(n, k) = map(int, input().split())
P = [*map(lambda x: int(x) - 1, input().split())]
C = [*map(int, input().split())]
score = -10 ** 18
for st in range(n):
	lap_sc = sum_sc = 0
	nx = st
	for lap_cn in range(1, max(n, k) + 1):
		lap_sc += C[nx]
		nx = P[nx]
		if nx == st:
			break
	lap_sc = max(0, lap_sc)
	for k_cn in range(1, k + 1):
		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)


(N, K) = map(int, input().split())
P_list = list(map(int, input().split()))
C_list = list(map(int, input().split()))
checked_list = [0 for _ in range(N)]
min_INF = -1 * 10 ** 10
max_score = min_INF
for i in range(N):
	if checked_list[i] == 1:
		continue
	posit = i
	loop_list = [posit]
	score_list = []
	for j in range(N):
		posit = P_list[posit] - 1
		if j == 0:
			score_list.append(C_list[posit])
		else:
			score_list.append(score_list[-1] + C_list[posit])
		if posit in loop_list:
			break
		loop_list.append(posit)
	len_loop = len(loop_list)
	max_score_list = max(score_list)
	around_score = score_list[-1]
	temp_score_base = 0
	if around_score > 0 and K // len_loop > 0:
		temp_score_base += (K // len_loop - 1) * around_score
	for k in range(len_loop):
		checked_list[loop_list[k]] = 1
		temp_max_score = temp_score_base
		rest_score = min_INF
		if around_score > 0 and K // len_loop > 0:
			rest_score = max(max_score_list, max(score_list[:K % len_loop], default=min_INF) + around_score)
		rest_score = max(max(score_list[:min(K, len_loop)]), rest_score)
		temp_max_score = temp_max_score + rest_score
		max_score = max(max_score, temp_max_score)
		now_score = score_list.pop(0)
		len_score = len(score_list)
		score_list = [score_list[l] - now_score for l in range(len_score)]
		score_list.append(score_list[-1] + now_score)
print(max_score)


import numpy as np

def parse():
	(_, k) = list(map(int, input().split()))
	p = list(map(int, input().split()))
	c = list(map(int, input().split()))
	pc = {i: (pi - 1, ci) for (i, (pi, ci)) in enumerate(zip(p, c))}
	return (k, pc)

def read_split():
	(k, pc) = parse()
	lst = [[]]
	lst[0].append(pc.pop(0))
	while True:
		if not pc:
			break
		(p, _) = lst[-1][-1]
		if p in pc:
			pcj = pc.pop(p)
			lst[-1].append(pcj)
		else:
			j = next(iter(list(pc.keys())))
			pcj = pc.pop(j)
			lst.append([pcj])
	return (k, [np.array([ls[1] for ls in lst_], dtype=np.long) for lst_ in lst])

def inner(n, k, s, sim):
	if sim.shape[1] == 1:
		return sim.max()
	if k < n or s <= 0:
		return sim.max()
	div = k // n
	mod = k % n
	if mod == 0:
		return s * (div - 1) + sim.max()
	else:
		return s * div + sim[:, :mod].max()

def main():
	(k, data_set) = read_split()
	result = min([d.min() for d in data_set])
	for data in data_set:
		n = data.size
		rep = np.repeat(data[None], 2, axis=0).flatten()
		sim = np.array([np.cumsum(rep[i:i + min(k, n)]) for i in range(n)])
		cand = inner(n, k, data.sum(), sim)
		result = max(result, cand)
	print(result)

def __starting_point():
	main()
__starting_point()


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

def calc(x):
	global n, k
	next = x
	ma = max_c
	s = 0
	l = []
	for i in range(n):
		next = p[next]
		s += c[next]
		l.append(c[next])
		ma = max(ma, s)
		if next == x:
			break
	if s <= 0:
		return ma
	cycle = k // (i + 1)
	rest = k % (i + 1)
	ans = (cycle - 1) * s + ma
	f = s * cycle
	for j in range(rest):
		f += l[j]
		ans = max(ans, f)
	return ans
A = max_c
for start in range(n):
	A = max(A, calc(start))
print(A)


from itertools import accumulate
(n, k) = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
c = list(map(int, input().split()))
ans = -10 ** 18
for i in range(n):
	pos = i
	scores = []
	while True:
		pos = p[pos]
		scores.append(c[pos])
		if pos == i:
			break
	m = len(scores)
	s = list(accumulate(scores))
	for j in range(min(m, k)):
		x = (k - j - 1) // m
		ans = max(ans, s[j], s[j] + s[-1] * x)
print(ans)


(N, K) = [int(x) for x in input().split()]
P = [int(x) - 1 for x in input().split()]
C = [int(x) for x in input().split()]
inf = float('inf')
ans = max(C)
for pos in range(N):
	i = pos
	score = 0
	cycleLen = None
	cycleGain = None
	bestInc = 0
	k = 0
	while k < K:
		i = P[i]
		score += C[i]
		ans = max(ans, score)
		if i == pos:
			cycleLen = k + 1
			numCycles = max(0, (K - k - cycleLen) // cycleLen)
			if k + numCycles * cycleLen < K:
				k += numCycles * cycleLen
				score += numCycles * score
		k += 1
print(ans)


import numpy as np

def main():
	(n, k) = list(map(int, input().split()))
	p = [int(i) - 1 for i in input().split()]
	c = [int(i) for i in input().split()]
	seen = set()
	loop_list = []
	for start in range(n):
		v = start
		loop = []
		while v not in seen:
			seen.add(v)
			loop.append(c[v])
			v = p[v]
		seen.add(v)
		if loop:
			loop_list.append(np.array(loop))
	ans = min(c)
	for loop in loop_list:
		loop_len = len(loop)
		loop_num = k // loop_len
		loop_mod = k % loop_len
		loop_sum = sum(loop)
		table = np.zeros((loop_len, loop_len), dtype=int)
		table[0] = loop.cumsum()
		table[:, -1] = loop_sum
		for i in range(loop_len - 1):
			table[i + 1, :-1] = (table[i] - loop[i])[1:]
		ans = max(table[:, :min(loop_len, k)].max(), ans)
		if loop_num > 0:
			ans = max(loop_sum * (loop_num - 1) + table[:, :loop_len].max(), ans)
			if loop_mod > 0:
				ans = max(loop_sum * loop_num + table[:, :loop_mod].max(), ans)
	print(ans)

def __starting_point():
	main()
__starting_point()


from itertools import accumulate

def solve(n, k, ppp, ccc):
	NINF = -10 ** 18
	ans = NINF
	checked = [False] * n
	for s in range(n):
		if checked[s] == True:
			continue
		checked[s] = True
		scores = [ccc[ppp[s]]]
		v = ppp[s]
		while v != s:
			scores.append(ccc[ppp[v]])
			checked[v] = True
			v = ppp[v]
		l = len(scores)
		(d, m) = divmod(k, l)
		loop = sum(scores)
		if d > 0:
			d -= 1
			m += l
		scores += scores * 2
		scores.insert(0, 0)
		acc = list(accumulate(scores))
		tmp = max((max(acc[i + 1:i + m + 1]) - acc[i] for i in range(l)))
		ans = max(ans, tmp, loop * d + tmp)
	return ans
(n, k) = list(map(int, input().split()))
ppp = list(map(int, input().split()))
ppp = [p - 1 for p in ppp]
ccc = list(map(int, input().split()))
print(solve(n, k, ppp, ccc))


(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 = max(c)
for i in range(n):
	f = i
	r = 0
	l = []
	while True:
		f = p[f]
		l.append(c[f])
		r += c[f]
		if f == i:
			break
	t = 0
	for j in range(len(l)):
		t += l[j]
		ret = t
		if r > 0:
			e = (k - j - 1) // len(l)
			ret += r * e
		ans = max(ans, ret)
print(ans)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
P = [i - 1 for i in P]
C = list(map(int, input().split()))
import math
ans = -10 ** 18
for i in range(N):
	x = i
	tot = 0
	cycle = []
	while True:
		x = P[x]
		cycle.append(C[x])
		tot += C[x]
		if x == i:
			break
	L = len(cycle)
	t = 0
	for i in range(L):
		t += cycle[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)


(n, k) = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))
maxsc = -1e+20
for s in range(1, n + 1):
	x = s
	sc = [0]
	i = 0
	while i < k:
		x = p[x]
		sc.append(sc[i] + c[x])
		i += 1
		if x == s:
			loop = i
			loopsc = sc[i]
			if loopsc > 0:
				baseup = loopsc * int((k - i) / loop)
				for j in range(loop):
					sc[j + 1] += baseup
				for j in range((k - i) % loop):
					sc[j + 1] += loopsc
			i = k
	sc[0] = -1e+20
	maxsc = max(maxsc, max(sc))
print(maxsc)


from collections import deque
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = -1000000000
for i in range(n):
	now = i
	j = 0
	score = deque([0])
	while j < k:
		score.append(score[j] + c[p[now] - 1])
		now = p[now] - 1
		j += 1
		if now == i:
			break
	ans = max(ans, max(list(score)[1:]))
	if j < k and score[-1] > 0:
		loop_num = k // j
		rest = k % j
		ans = max(ans, max(list(score)[:rest + 1]) + loop_num * score[-1])
		ans = max(ans, max(list(score)) + (loop_num - 1) * score[-1])
print(ans)


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = -10 ** 10
for i in range(n):
	loop = [0]
	now = i
	while True:
		now = p[now] - 1
		loop.append(loop[-1] + c[now])
		if now == i:
			break
	L = len(loop) - 1
	if k <= L:
		score = max(loop[1:k + 1])
		ans = max(score, ans)
	else:
		score = max(loop[-1], 0) * (k // L - 1)
		ans = max(ans, score)
		for j in range(k % L + L):
			score += loop[j % L + 1] - loop[j % L]
			ans = max(score, ans)
print(ans)


import os
import sys
import math
import heapq
from decimal import *
from io import BytesIO, IOBase
from collections import defaultdict, deque

def r():
	return int(input())

def rm():
	return map(int, input().split())

def rl():
	return list(map(int, input().split()))
(n, k) = rm()
p = rl()
p = [0] + p
c = rl()
c = [0] + c
b = [-1] * (n + 1)
give = 0
ans = -math.inf
for i in range(1, n + 1):
	a = i
	lenn = 1
	add = c[i]
	while p[a] != i:
		add += c[p[a]]
		lenn += 1
		a = p[a]
	if add < 0:
		add = 0
	addAgain = 0
	a = i
	for j in range(lenn):
		if j > k:
			break
		addAgain += c[a]
		ans = max(ans, addAgain + add * ((k - j - 1) // lenn))
		a = p[a]
print(ans)


(n, k) = (int(x) for x in input().split())
P = list((int(x) - 1 for x in input().split()))
C = list((int(x) for x in input().split()))
ans = -1e+18
for si in range(n):
	S = [C[si]]
	x = P[si]
	while x != si:
		S.append(S[-1] + C[x])
		x = P[x]
	m = len(S)
	if k <= m:
		tmp = max(S[:k])
	else:
		loop = k // m
		r = k % m
		tmp = max(S[-1] * (loop - 1) + max(S), max(S))
		if r != 0:
			tmp = max(tmp, S[-1] * loop + max(S[:r]))
	ans = max(ans, tmp)
print(ans)


((n, k), p, c) = [[*map(int, t.split())] for t in open(0)]
a = -9000000000.0
for i in range(n):
	s = f = 0
	(x, j, *l) = (i, k)
	while ~f:
		x = p[x] - 1
		s += c[x]
		l += (s,)
		f -= x == i
	for t in l[:k]:
		j -= 1
		a = max(a, t + j // len(l) * s * (s > 0))
print(a)


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


(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):
	hoge = []
	p = i
	s = 0
	for j in range(K):
		p = P[p] - 1
		s += C[p]
		hoge.append(s)
		ans = max(ans, s)
		if p == i:
			S1 = s * ((K - 1) // len(hoge))
			S1 += max(hoge[0:(K - 1) % len(hoge) + 1])
			S2 = ans
			if (K - 1) // len(hoge) > 1:
				S2 = s * ((K - 1) // len(hoge) - 1)
				S2 += max(hoge)
			ans = max(ans, S1, S2)
			break
print(ans)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
for i in range(len(P)):
	P[i] -= 1
ans = float('-inf')
for i in range(N):
	cycle = []
	pos = i
	total = 0
	while True:
		pos = P[pos]
		cycle.append(C[pos])
		total += C[pos]
		if pos == i:
			break
	l = len(cycle)
	t = 0
	for j in range(l):
		t += cycle[j]
		if j + 1 > K:
			break
		now = t
		if total > 0:
			cnt = (K - j - 1) // l
			now += total * cnt
		ans = max(ans, now)
print(ans)


from itertools import accumulate
import sys
sys.setrecursionlimit(10 ** 6)
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))

def dfs(G, v, p):
	seen[v] = True
	sc.append(c[v])
	for nv in G[v]:
		if nv == p:
			continue
		if seen[nv]:
			pos[0] = nv
			return
		dfs(G, nv, v)
		if pos[0] != -1:
			return
G = [[] for _ in range(n)]
for i in range(n):
	G[i].append(p[i] - 1)
seen = [False] * n
ans = -float('inf')
for i in range(n):
	if seen[i] == False:
		pos = [-1]
		sc = []
		dfs(G, i, -1)
		if sc:
			sumsc = sum(sc)
			lenc = len(sc)
			for j in range(lenc):
				if j != 0:
					sc = sc[1:] + [sc[0]]
				ac = list(accumulate(sc))
				if sumsc <= 0:
					ans = max(ans, max(ac[:min(k, lenc)]))
				elif k % lenc == 0:
					ans = max(ans, ac[-1] * (k // lenc - 1) + max(ac))
				else:
					ans = max(ans, ac[-1] * (k // lenc) + max(ac[:k % lenc]))
print(ans)


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = -10 ** 18
flag = dict()
for i in range(n):
	if i in flag:
		continue
	cur = i
	accum = []
	flag[cur] = 0
	s = 0
	while flag[cur] < 2:
		cur = p[cur] - 1
		s += c[cur]
		accum.append(s)
		if cur not in flag:
			flag[cur] = 0
		else:
			flag[cur] += 1
	l = len(accum) // 2
	loop = accum[l - 1]
	accum = [0] + accum
	for x in range(1, l + 1):
		if loop <= 0 or k // l < 1:
			ans = max(ans, max(accum[x:x + min(k, l)]) - accum[x - 1])
		else:
			a = max(accum[x:x + l - 1]) - accum[x - 1]
			d = accum[x + l - 1] - accum[x - 1]
			if k % l != 0:
				b = max(accum[x:x + k % l]) - accum[x - 1]
				ans = max(ans, max(k // l * d, k // l * d + b, (k // l - 1) * d + a))
			else:
				b = max(accum[x:x + l - 1]) - accum[x - 1]
				ans = max(ans, max(k // l * d, (k // l - 1) * d + a))
print(ans)


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


(N, K) = map(int, input().split())
(P, C) = [list(map(int, input().split())) for i in range(2)]
r = -10 ** 18
for j in range(N):
	d = [0] * (N + 1)
	p = j
	for i in range(N):
		p = P[p] - 1
		d[i + 1] = d[i] + C[p]
		if p == j:
			break
	q = max(d[1:K + 1]) if K < i + 1 else max(d[1:i + 1]) if d[i + 1] < 0 else max(max(d) + d[i + 1] * (K // (i + 1) - 1), max(d[:K % (i + 1) + 1]) + d[i + 1] * (K // (i + 1)))
	r = max(r, q)
print(r)


(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

def score(a, k):
	now = p[a]
	s = c[now]
	cnt = 1
	l = [s]
	while now != a and cnt < k:
		now = p[now]
		s += c[now]
		l.append(s)
		cnt += 1
	if cnt == k:
		return max(l)
	l.append((k // cnt - 1) * s + max(l))
	s = k // cnt * s
	k %= cnt
	cnt = 0
	while cnt < k:
		now = p[now]
		s += c[now]
		l.append(s)
		cnt += 1
	return max(l)
print(max((score(i, k) for i in range(n))))


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


(n, k) = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
c = list(map(int, input().split()))
score = [0] * (n + 1)
max_score = -10 ** 9
for i in range(n):
	x = i
	temp_max = [-10 ** 9] * (n + 1)
	for j in range(1, n + 1):
		score[j] = score[j - 1] + c[p[x]]
		temp_max[j] = max(temp_max[j - 1], score[j])
		x = p[x]
		if x == i:
			break
	if j >= k:
		max_score = max(max_score, temp_max[k])
	elif score[j] < 0:
		max_score = max(max_score, temp_max[j])
	else:
		m = k // j
		a = score[j] * (m - 1) + temp_max[j]
		b = score[j] * m + temp_max[k % j]
		max_score = max(max_score, a, b)
print(max_score)


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


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
score = [[] for _ in range(n)]
for i in range(1, n + 1):
	x = [i]
	s = 0
	while True:
		x.append(p[x[-1] - 1])
		s += c[x[-1] - 1]
		score[i - 1].append(s)
		if x[-1] == i:
			break
ans = -1e+20
for i in range(n):
	l = len(score[i])
	for j in range(min(k, l)):
		tmp = score[i][j]
		if 0 < score[i][-1]:
			tmp += (k - j - 1) // l * score[i][-1]
		ans = max(tmp, ans)
print(ans)


import sys

def main():
	input = sys.stdin.readline
	(n, k) = map(int, input().split())
	p_list = list(map(int, input().split()))
	c_list = list(map(int, input().split()))
	res = -float('inf')
	for s in range(n):
		S = []
		i = p_list[s] - 1
		S.append(c_list[i])
		while i != s:
			i = p_list[i] - 1
			S.append(S[-1] + c_list[i])
		if k <= len(S):
			score = max(S[:k])
		elif S[-1] <= 0:
			score = max(S)
		else:
			score1 = S[-1] * (k // len(S) - 1)
			score1 += max(S)
			score2 = S[-1] * (k // len(S))
			r = k % len(S)
			if r != 0:
				score2 += max(0, max(S[:r]))
			score = max(score1, score2)
		res = max(res, score)
	print(res)
main()


(n, k) = map(int, input().split())
pn = list(map(int, input().split()))
cn = list(map(int, input().split()))
ans = -float('inf')
for i in range(n):
	start = i
	now = start
	total = 0
	ls = [0]
	for j in range(1, k + 1):
		now = pn[now] - 1
		total += cn[now]
		ans = max(ans, total)
		ls.append(total)
		if now == start:
			rp = j
			break
	else:
		continue
	if total <= 0:
		continue
	elif k % rp == 0:
		s = k % rp
		ans2 = total * (k // rp - 1) + max(ls)
		ans = max(ans, ans2)
	else:
		s = k % rp
		ans2 = total * (k // rp) + max(ls[:s + 1])
		ans = max(ans, ans2)
print(ans)


(N, K) = map(int, input().split())
P = [int(a) - 1 for a in input().split()]
C = [int(a) for a in input().split()]
ans = -float('inf')
for si in range(N):
	x = si
	S = []
	tot = 0
	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)


(n, k) = map(int, input().split())
p = [int(x) - 1 for x in input().split()]
c = [int(x) for x in input().split()]
pow_num = 31
point = [[0] * n for i in range(pow_num)]
point_max = [[0] * n for i in range(pow_num)]
posi = [[0] * n for i in range(pow_num)]
c_set = set(c)
if all([i < 0 for i in c_set]):
	print(max(c_set))
else:
	for i in range(pow_num):
		if i == 0:
			for j in range(n):
				posi[i][j] = p[j]
				point[i][j] = c[p[j]]
			continue
		for j in range(n):
			posi[i][j] = posi[i - 1][posi[i - 1][j]]
			point[i][j] = point[i - 1][j] + point[i - 1][posi[i - 1][j]]
	for i in range(pow_num):
		if i == 0:
			for j in range(n):
				point_max[i][j] = point[i][j]
			continue
		for j in range(n):
			point_max[i][j] = max(point_max[i - 1][j], point[i - 1][j] + point_max[i - 1][posi[i - 1][j]])
	power_count = list()
	for i in range(pow_num):
		if k & 1 << i:
			power_count.append(i)
		ans = 0
		for i in range(n):
			next_posi = i
			cumsum_point = 0
			for posi_idx in power_count:
				if ans < cumsum_point + point_max[posi_idx][next_posi]:
					ans = cumsum_point + point_max[posi_idx][next_posi]
				cumsum_point += point[posi_idx][next_posi]
				next_posi = posi[posi_idx][next_posi]
	print(ans)


(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = -10 ** 9
for i in range(N):
	tmp_max = [-10 ** 9] * (N + 1)
	total = 0
	current_block = P[i]
	for j in range(1, N + 1):
		total += C[current_block]
		tmp_max[j] = max(tmp_max[j - 1], total)
		if current_block == i:
			break
		current_block = P[current_block]
	if total <= 0:
		ans = max(ans, tmp_max[j])
	else:
		n = K // j
		r = K % j
		if r == 0:
			ans = max(ans, total * (n - 1) + tmp_max[j])
		else:
			ans = max(ans, total * n + tmp_max[r])
print(ans)


(n, k) = map(int, input().split())
p = [int(i) - 1 for i in input().split()]
c = list(map(int, input().split()))
ans = -10 ** 9
for i in range(n):
	start = i
	cycle = [0]
	for _ in range(n):
		i = p[i]
		cycle += [cycle[-1] + c[i]]
		if i == start:
			break
	(S, L) = (cycle[-1], len(cycle) - 1)
	if S <= 0:
		ans = max(ans, max(cycle[1:k + 1]))
	elif k > L:
		ans = max(ans, (k // L - 1) * S + max(max(cycle), max(cycle[:k % L + 1]) + S))
	else:
		ans = max(ans, max(cycle[:k + 1]))
print(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):
	s = []
	j = p[i] - 1
	s.append(c[j])
	while j != i:
		j = p[j] - 1
		s.append(s[-1] + c[j])
	l = len(s)
	if k <= l:
		a = max(s[:k])
	elif s[-1] <= 0:
		a = max(s)
	else:
		(w, r) = divmod(k, l)
		a1 = s[-1] * (w - 1) + max(s)
		a2 = s[-1] * w
		if r != 0:
			a2 += max(0, max(s[:r]))
		a = max(a1, a2)
	ans = max(ans, a)
print(ans)


(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = 10 ** 20 * -1
for si in range(N):
	x = si
	s = []
	tot = 0
	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)


ni = lambda : int(input())
nm = lambda : map(int, input().split())
nl = lambda : list(map(int, input().split()))
(n, k) = nm()
p = nl()
c = nl()
for i in range(n):
	p[i] -= 1
ans = -10 ** 18
for si in range(n):
	x = si
	s = []
	tot = 0
	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)


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


(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = -10 ** 29
for start in range(N):
	now = start
	point = 0
	for j in range(K):
		now = P[now]
		point += C[now]
		ans = max(ans, point)
		if now == start:
			break
	loop_cnt = j + 1
	left_k = K - loop_cnt
	if point < 0:
		continue
	tmp = point
	point *= left_k // loop_cnt + 1
	point -= tmp
	ans = max(ans, point)
	for j in range(left_k % loop_cnt + loop_cnt):
		now = P[now]
		point += C[now]
		ans = max(ans, point)
print(ans)


from collections import Counter
from heapq import heapify, heappop, heappush
from itertools import accumulate

def solve(n, k, ppp, ccc):
	NINF = -10 ** 18
	ans = NINF
	checked = [False] * n
	for s in range(n):
		if checked[s] == True:
			continue
		checked[s] = True
		scores = [ccc[ppp[s]]]
		v = ppp[s]
		while v != s:
			scores.append(ccc[ppp[v]])
			checked[v] = True
			v = ppp[v]
		l = len(scores)
		(d, m) = divmod(k, l)
		loop = sum(scores)
		if d > 0:
			d -= 1
			m += l
		scores += scores * 2
		scores.insert(0, 0)
		acc = list(accumulate(scores))
		base = max(0, loop * d)
		range_max = [-a for a in acc[1:m + 1]]
		available_max = Counter(range_max)
		heapify(range_max)
		for i in range(l):
			while available_max[range_max[0]] == 0:
				heappop(range_max)
			ans = max(ans, base - range_max[0] - acc[i])
			old = -acc[i + 1]
			new = -acc[i + m + 1]
			available_max[old] -= 1
			available_max[new] += 1
			heappush(range_max, new)
	return ans
(n, k) = list(map(int, input().split()))
ppp = list(map(int, input().split()))
ppp = [p - 1 for p in ppp]
ccc = list(map(int, input().split()))
print(solve(n, k, ppp, ccc))


from sys import stdin
nii = lambda : map(int, stdin.readline().split())
lnii = lambda : list(map(int, stdin.readline().split()))
(n, k) = nii()
p = lnii()
c = lnii()
ans = -10 ** 18
for i in range(n):
	ini_x = i
	x = i
	point = []
	t_ans = 0
	cnt = 0
	t_max = -10 ** 18
	while True:
		x = p[x] - 1
		t_point = c[x]
		point.append(t_point)
		t_ans += t_point
		t_max = max(t_max, t_ans)
		cnt += 1
		if x == ini_x:
			break
	if t_ans < 0:
		ans = max(ans, t_max)
	else:
		num = k // cnt
		num -= 1
		zan = k - num * cnt
		c_ans = t_ans * num
		for j in range(zan):
			x = p[x] - 1
			c_ans += c[x]
			ans = max(ans, c_ans)
print(ans)


from itertools import accumulate
import sys
sys.setrecursionlimit(10 ** 8)
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
p = [i - 1 for i in p]
seen = [False] * n
ans = -float('inf')
for i in range(n):
	if not seen[i]:
		sc = []
		stop = i
		while True:
			seen[i] = True
			sc.append(c[i])
			if p[i] == stop:
				break
			i = p[i]
		lens = len(sc)
		for j in range(lens):
			if j != 0:
				sc = sc[1:] + [sc[0]]
			ac = list(accumulate(sc))
			if sum(sc) <= 0:
				ans = max(ans, max(ac[:min(k, lens)]))
			elif k % lens == 0:
				ans = max(ans, ac[-1] * (k // lens - 1) + max(ac))
			else:
				ans = max(ans, ac[-1] * (k // lens) + max(ac[:k % lens]))
print(ans)


from math import inf
(n, k) = map(int, input().split())
arr = [0] + list(map(int, input().split()))
cost = [0] + list(map(int, input().split()))
ma = -inf
for i in range(1, n + 1):
	se = set()
	cur = i
	pref = [0]
	f = 0
	while cur not in se and f < k:
		se.add(cur)
		cur = arr[cur]
		co = cost[cur]
		pref.append(pref[-1] + co)
		ma = max(ma, pref[-1])
		f += 1
	if pref[-1] > 0 and k >= f:
		ans = pref[-1] * (k // f)
		for j in range(k % f + 1):
			ma = max(ma, ans + pref[j])
		ma = max(ma, pref[-1] * (k // f - 1) + max(pref))
print(ma)


(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 = -10 ** 18
for si in range(N):
	x = si
	c = []
	tot = 0
	while True:
		x = P[x]
		c.append(C[x])
		tot += C[x]
		if x == si:
			break
	s = 0
	for k in range(len(c)):
		if k + 1 > K:
			break
		s += c[k]
		ss = s
		if tot > 0:
			ss += tot * int((K - (k + 1)) // len(c))
		ans = max(ss, ans)
print(ans)


(n, k) = map(int, input().split())
pp = list(map(int, input().split()))
p = [pp[i] - 1 for i in range(n)]
c = list(map(int, input().split()))
ans = -(10 ** 9 + 1)
for i in range(n):
	s = 0
	x = i
	for j in range(k):
		x = p[x]
		s += c[x]
		ans = max(ans, s)
		if i == x:
			break
	a = int(k / (j + 1))
	m = k % (j + 1)
	if m == 0 and a > 1:
		m = j + 1
		a -= 1
	s *= a
	ans = max(ans, s)
	for l in range(m):
		x = p[x]
		s += c[x]
		ans = max(ans, s)
print(ans)


(N, K) = map(int, input().split())
P = list(map(lambda s: int(s) - 1, input().split()))
C = list(map(int, input().split()))
ans = -1000000000
for i in range(N):
	S = [C[i]]
	p = P[i]
	while p != i:
		S.append(C[p])
		p = P[p]
	s = sum(S)
	n = len(S)
	acc = 0
	for i in range(min(n, K + 2)):
		acc += S[i]
		a = acc
		if s > 0:
			a += s * ((K - (i + 1)) // n)
		ans = max(a, ans)
print(ans)


(n, k) = map(int, input().split())
P = tuple(map(lambda x: int(x) - 1, input().split()))
C = tuple(map(int, input().split()))
from collections import deque
ans = -2 * 10 ** 9
for (idx, root) in enumerate(P):
	scores = [C[root]]
	p = P[root]
	while True:
		scores.append(scores[-1] + C[p])
		p = P[p]
		if p == root:
			break
	sc = scores[-1]
	if sc <= 0:
		if k < len(scores):
			ans = max(ans, max(scores[:k]))
		else:
			ans = max(ans, max(scores))
	else:
		(kk, r) = divmod(k, len(scores))
		if r == 0:
			ans = max(ans, kk * sc, (kk - 1) * sc + max(scores))
		else:
			ans = max(ans, kk * sc + max(scores[:r]))
print(ans)


import itertools

def __starting_point():
	(N, K) = list(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 = []
	cycleID = 0
	procCnt = 0
	for n in range(N):
		v = n
		if cycleIDs[v] != -1:
			continue
		else:
			currentCycleCosts = []
			while True:
				currentCycleCosts.append(C[v])
				cycleIDs[v] = cycleID
				v = P[v]
				if cycleIDs[v] != -1:
					procCnt = K % len(currentCycleCosts)
					if len(currentCycleCosts) + procCnt <= K:
						procCnt += len(currentCycleCosts)
					cycleInfs.append((procCnt, len(currentCycleCosts), currentCycleCosts * 3))
					cycleID += 1
					break
	ans = -10 ** 9
	for (procCnt, currentCycleSize, currentCycleCosts) in cycleInfs:
		loopScore = 0
		if sum(currentCycleCosts) > 0:
			cycleLoopCnt = (K - procCnt) // currentCycleSize
			loopScore = cycleLoopCnt * sum(currentCycleCosts[:currentCycleSize])
		for i in range(currentCycleSize):
			score = max(itertools.accumulate(currentCycleCosts[i:i + procCnt]))
			if ans < score + loopScore:
				ans = score + loopScore
	print(ans)
__starting_point()


def max2(x, y):
	return x if x > y else y
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
off = max(C)
m2 = off
for i in range(N):
	tmp = 0
	m1 = off
	l = i
	S = 0
	k = 0
	for j in range(N):
		S += C[l]
		l = P[l] - 1
		if l == i:
			k = j + 1
			break
	cnt = K // k - (K % k == 0)
	cnt = max2(0, cnt - 2)
	a = K - cnt * k
	l = i
	for j in range(a):
		tmp += C[l]
		m1 = max2(m1, tmp)
		l = P[l] - 1
	if S > 0:
		m1 += cnt * S
	m2 = max2(m1, m2)
print(m2)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
seen = set()
circuits = []
for x in range(N):
	cir = []
	point = 0
	while True:
		if x in seen:
			if cir != []:
				circuits.append((cir, point))
			break
		seen.add(x)
		point += C[x]
		cir.append(x)
		x = P[x] - 1
ans = -1000000000000
for x in circuits:
	tmp = 0
	if K >= len(x[0]) * 2:
		if x[1] > 0:
			tmp = (K // len(x[0]) - 1) * x[1]
		r = K % len(x[0]) + len(x[0])
	else:
		r = K
	for y in x[0]:
		tmp2 = 0
		for _ in range(r):
			y = P[y] - 1
			tmp2 += C[y]
			ans = max(ans, tmp + tmp2)
print(ans)


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.141592653589793

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


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = -float('inf')
for s in range(N):
	scores = [0] * (N + 1)
	i = P[s]
	v = scores[i] = C[i]
	l = 1
	while i != s:
		i = P[i]
		v += C[i]
		scores[i] = v
		l += 1
	i = P[s]
	c = 1
	ans = max(ans, scores[i], scores[i] + (K - c) // l * v)
	while i != s and c < K:
		i = P[i]
		c += 1
		ans = max(ans, scores[i], scores[i] + (K - c) // l * v)
print(ans)


INF = 10 ** 9
f = lambda : [*map(int, input().split())]
(n, k) = f()
(p, c) = (f(), f())
p = [*map(lambda x: x - 1, p)]
tp = [[*range(n)] for _ in range(n + 1)]
tc = [[0] * n for _ in range(n + 1)]
lt = [0] * n
lc = [0] * n
for i in range(n):
	for j in range(n):
		t = p[tp[i][j]]
		tp[i + 1][j] = t
		tc[i + 1][j] = tc[i][j] + c[t]
		if t == j and lt[j] == 0:
			lt[j] = i + 1
			lc[j] = tc[i + 1][j]
a = -INF
for i in range(n):
	if lc[i] < 1 or k <= lt[i]:
		for j in range(min(lt[i], k)):
			a = max(a, tc[j + 1][i])
	else:
		for j in range(lt[i]):
			t = k // lt[i] * lc[i] + tc[j + 1][i]
			if k % lt[i] < j + 1:
				t -= lc[i]
			a = max(a, t)
print(a)


(N, K) = map(int, input().split())
(*P,) = map(int, input().split())
(*C,) = map(int, input().split())
ans = -float('inf')
v = []
for n in range(N):
	(loop, score) = (0, 0)
	t = n
	for i in range(min(N, K)):
		n = P[n] - 1
		score += C[n]
		ans = max(ans, score)
		if n == t:
			loop = i + 1
			break
	v.append((loop, score))
for n in range(N):
	(loop, score) = v[n]
	if loop > 0 and score > 0:
		r = (K - 1) // loop
		nscore = r * score
		for i in range(K - r * loop):
			n = P[n] - 1
			nscore += C[n]
			ans = max(nscore, ans)
print(ans)


(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 = -10000000000
for start in range(n):
	now = start
	pt = 0
	cycle = 0
	looplen = 0
	while 1:
		now = p[now]
		pt += c[now]
		looplen += 1
		if now == start:
			break
	cycle = pt
	pt = 0
	for i in range(looplen):
		now = p[now]
		pt += c[now]
		aftermove = k - i - 1
		if aftermove < 0:
			continue
		loop = aftermove // looplen
		ans = max(ans, pt)
		ans = max(ans, pt + loop * cycle)
print(ans)


INF = 10 ** 20
(N, K) = map(int, input().split())
array = list(map(int, input().split()))
P = []
C = list(map(int, input().split()))
for i in array:
	P.append(i - 1)
ans = -1 * INF
for i in range(N):
	v = i
	cycle_sum = 0
	cycle_cnt = 0
	while True:
		cycle_cnt += 1
		cycle_sum += C[v]
		v = P[v]
		if v == i:
			break
	path = 0
	cnt = 0
	while True:
		cnt += 1
		path += C[v]
		if cnt > K:
			break
		num = (K - cnt) // cycle_cnt
		score = path + max(0, cycle_sum) * num
		ans = max(ans, score)
		v = P[v]
		if v == i:
			break
print(ans)


(n, k) = [int(x) for x in input().split()]
p = [int(x) - 1 for x in input().split()]
c = [int(x) for x in input().split()]
ans = max(c)
if ans < 0:
	print(ans)
	exit()
for i in range(n):
	nxt = i
	lp = []
	while 1:
		nxt = p[nxt]
		lp.append(nxt)
		if nxt == i:
			break
	lpc = sum((c[x] for x in lp))
	nxt = i
	lpl = len(lp)
	wks = 0
	for j in range(lpl):
		nxt = p[nxt]
		wks += c[nxt]
		ans = max(ans, (k - j - 1) // lpl * max(0, lpc) + wks)
		if j == k - 1:
			break
print(ans)


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
l = [[] for i in range(n)]
for i in range(n):
	l2 = [i + 1]
	cnt = 0
	while True:
		l2.append(p[l2[-1] - 1])
		cnt += c[l2[-1] - 1]
		l[i].append(cnt)
		if l2[-1] == i + 1:
			break
ans = -float('inf')
for i in range(n):
	le = len(l[i])
	for j in range(min(k, le)):
		cnt = l[i][j]
		if l[i][-1] > 0:
			cnt += (k - j - 1) // le * l[i][-1]
		ans = max(ans, cnt)
print(ans)


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


((n, k), p, c) = [[*map(int, i.split())] for i in open(0)]

def solve(x, t):
	visit = [0] * n
	visit[x] = 1
	loop = [0] * n
	count = 0
	ans = c[p[x] - 1]
	l = True
	sub = 0
	while True:
		x = p[x] - 1
		if l:
			if visit[x]:
				if loop[x]:
					ln = sum(loop)
					if t > l:
						sub += (t // ln - 1) * count * (count > 0)
						t %= ln
						t += ln
					l = False
				count += c[x]
				loop[x] = 1
			visit[x] = 1
		sub += c[x]
		t -= 1
		ans = max(sub, ans)
		if t < 1:
			return ans
print(max((solve(i, k) for i in range(n))))


def main():
	(N, K) = map(int, input().split())
	P = list(map(int, input().split()))
	P = [x - 1 for x in P]
	C = list(map(int, input().split()))
	ans = -10 ** 18
	for i in range(N):
		j = i
		S = 0
		L = 0
		for _ in range(K):
			j = P[j]
			S += C[j]
			L += 1
			ans = max(ans, S)
			if j == i:
				break
		if j == i:
			M = max(0, K // L - 1)
			T = S * M
			for _ in range(M * L, K):
				j = P[j]
				T += C[j]
				ans = max(ans, T)
	print(ans)
main()


import sys
input = sys.stdin.readline
(n, K) = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
c = list(map(int, input().split()))
if K == 1:
	print(max(c))
	exit()
ans = -10 ** 10

def cycle(k):
	mo = k
	clen = 0
	cscore = 0
	flg = True
	cmax = [-10 ** 10]
	while mo != k or flg:
		clen += 1
		cscore += c[mo]
		mo = p[mo]
		cmax.append(max(cmax[-1], cscore))
		if mo == k:
			flg = False
	if cscore < 0:
		return cmax[min(K - 1, clen - 1)]
	return cscore * ((K - 1) // clen) + cmax[(K - 1) % clen + 1]
for i in range(n):
	a = cycle(i)
	if a > ans:
		ans = a
print(ans)


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

def get(pos):
	used = [-1] * N
	cost = [0] * (N + 1)
	for k in range(N + 1):
		if k:
			cost[k] = cost[k - 1] + C[pos]
		if used[pos] >= 0:
			loop_size = k - used[pos]
			break
		used[pos] = k
		pos = P[pos] - 1
	if cost[loop_size] <= 0:
		return max(cost[1:K + 1])
	else:
		(a, b) = divmod(K, loop_size)
		v1 = cost[loop_size] * (a - 1) + max(cost[:K + 1])
		v2 = cost[loop_size] * a + max(cost[:b + 1])
		return max(v1, v2) if a else v2
ans = max([get(i) for i in range(N)])
print(ans)


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


(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 = -float('inf')
for i in range(n):
	snp = P[i]
	r = C[snp]
	L = [r]
	c = 0
	np = P[snp]
	while True:
		if c == k - 1:
			ANS = max(max(L), ANS)
			break
		if np == snp:
			y = k % (c + 1)
			m = k // (c + 1)
			if y == 0:
				ANS = max(max(L), max(L) + (m - 1) * L[-1], ANS)
				break
			else:
				ANS = max(max(L), max(max(L[:y]), 0) + m * L[-1], ANS)
				break
		r += C[np]
		L.append(r)
		np = P[np]
		c += 1
print(ANS)


(N, K) = map(int, input().split())
PList = list(map(int, input().split()))
CList = list(map(int, input().split()))
ans = -1 * 10 ** 18
for si in range(N):
	x = si
	s = list()
	total = 0
	l = 0
	while 1:
		x = PList[x] - 1
		s.append(CList[x])
		l += 1
		total += CList[x]
		if x == si:
			break
	t = 0
	for i in range(l):
		t += s[i]
		if i + 1 > K:
			break
		now = t
		if total > 0:
			e = (K - i - 1) // l
			now += total * e
		ans = max(ans, now)
print(ans)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
A = []
S = []
p = 2 ** N - 1
for i in range(N):
	if p >> i & 1:
		s = i + 1
		tmp = [C[i]]
		while s != P[i]:
			i = P[i] - 1
			tmp.append(C[i])
			p ^= 1 << i
		A.append(tmp)
		S.append(sum(tmp))
ans = -1 * 10 ** 9 - 1
for i in range(len(A)):
	a = A[i]
	n = len(a)
	s = S[i]
	for j in range(n):
		t = 0
		k = n
		if K > n:
			if s > 0:
				k = K % n
				if k == 0:
					k = n
					t = s * (K // n - 1)
				else:
					k = K % n
					t = s * (K // n)
		else:
			k = K
		for jj in range(j, k + j):
			if jj >= n:
				jj -= n
			t += a[jj]
			ans = max(ans, t)
		ans = max(ans, t)
print(ans)


import sys
input = sys.stdin.readline
(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):
	now = i
	visit = [False] * N
	visit[now] = True
	l = []
	for _ in range(N + 10):
		nex = P[now] - 1
		l.append(C[nex])
		if visit[nex]:
			break
		visit[nex] = True
		now = nex
	s = sum(l)
	now = 0
	for i in range(min(K, len(l))):
		now += l[i]
		ans = max(ans, now + (K - i - 1) // len(l) * max(0, s))
print(ans)


(N, K) = list(map(int, input().split()))
P = list(map(int, input().split()))
C = list(map(int, input().split()))
res = -10 ** 10
for i in range(N):
	j = i
	total = 0
	loop_values = []
	while True:
		j = P[j] - 1
		loop_values.append(C[j])
		total += C[j]
		if j == i:
			break
	loop_length = len(loop_values)
	point_sum = 0
	for j in range(loop_length):
		point_sum += loop_values[j]
		result_cand = point_sum
		if j + 1 > K:
			break
		if total > 0:
			loop_num = (K - j - 1) // loop_length
			result_cand += total * loop_num
		if res < result_cand:
			res = result_cand
print(res)


from math import inf
from sys import setrecursionlimit
setrecursionlimit(10 ** 4)
(N, K) = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))

class Graph(list):

	def __init__(self, n):
		super().__init__([None] * (n + 1))
		self.directions = P
		self.points = C
		self.loops = []
		self.loopscores = []
		self.search()
		self.evalloop()

	def search(self):
		for i in range(1, len(self)):
			self.history = set()
			self.goto(i)

	def goto(self, i):
		if self[i]:
			return self[i]
		if i in self.history:
			return self.addloop(i)
		self.history.add(i)
		(l, p) = self.goto(self.directions[i])
		if self[i] == None:
			self[i] = (l, p + 1)
		return self[i]

	def addloop(self, j):
		loop = [j]
		k = self.directions[j]
		while j != k:
			loop.append(k)
			k = self.directions[k]
		self.loops.append(loop)
		l = len(self.loops) - 1
		for i in loop:
			self[i] = (l, 0)
		return (l, 0)

	def maxscore(self):
		return max((self.score(self.directions[i], K) for i in range(1, len(self))))

	def score(self, i, k):
		if k == 0:
			return 0
		p = self.points[i]
		i = self.directions[i]
		k -= 1
		if self[i][1] > 0:
			s = self.score(i, k)
			return p + max(0, s)
		n = self[i][0]
		loop = self.loops[n]
		j = loop.index(i)
		base = self.base[n]
		loopscore = base[-1]
		leftmax = self.leftmax[n]
		rightmax = self.rightmax[n]
		length = len(loop)
		(d, m) = divmod(k, length)
		if m == 0:
			s = 0
		elif j + m < length:
			if leftmax[j] < leftmax[j + m]:
				s = leftmax[j + m] - base[j]
			elif rightmax[j + 1] > rightmax[j + m + 1]:
				s = rightmax[j + 1] - base[j]
			else:
				s = max(base[j + 1:j + m + 1]) - base[j]
		else:
			s = max(loopscore + leftmax[j + m - length], rightmax[j + 1]) - base[j]
		if d:
			t = max(loopscore + leftmax[j], rightmax[j + 1]) - base[j]
			return max(0, s, s + loopscore * d, t, t + loopscore * (d - 1)) + p
		else:
			return max(0, s, s + loopscore * d) + p

	def evalloop(self):
		(b, c, d) = ([], [], [])
		for l in self.loops:
			(bb, cc, dd) = ([0], [-inf], [-inf])
			for i in l:
				bb.append(bb[-1] + self.points[i])
			for v in bb:
				cc.append(max(cc[-1], v))
			for v in reversed(bb):
				dd.append(max(dd[-1], v))
			b.append(bb)
			c.append(cc[1:])
			d.append(list(reversed(dd[1:])))
		self.base = b
		self.leftmax = c
		self.rightmax = d
g = Graph(N)
print(g.maxscore())


(n, k) = map(int, input().split())
p = list(map(lambda z: int(z) - 1, input().split()))
c = list(map(int, input().split()))
data = [[0 for i in range(n + 1)] for j in range(n)]
loop = [10 ** 10 for i in range(n)]
for i in range(n):
	j = i
	for t in range(1, n + 1):
		j = p[j]
		data[i][t] += data[i][t - 1] + c[j]
		if j == i:
			loop[i] = min(loop[i], t)
ans = -10 ** 10
for i in range(n):
	for j in range(1, min(n, k) + 1):
		if j > loop[i]:
			break
		if data[i][loop[i]] <= 0:
			ans = max(ans, data[i][j])
		else:
			ans = max(ans, data[i][loop[i]] * ((k - j) // loop[i]) + data[i][j])
print(ans)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
P = list(map(lambda x: x - 1, P))
C = list(map(int, input().split()))
ans = -float('inf')
for i in range(N):
	st = i
	tmp = 0
	for j in range(K):
		st = P[st]
		tmp += C[st]
		ans = max(ans, tmp)
		if i == st:
			break
	(s, v) = divmod(K, j + 1)
	if s > 1 and v == 0:
		s -= 1
		v = j + 1
	tmp *= s
	ans = max(ans, tmp)
	for j in range(v):
		st = P[st]
		tmp += C[st]
		ans = max(ans, tmp)
print(ans)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
_c = list(map(int, input().split()))
C = [0] * N
for i in range(N):
	P[i] -= 1
	C[i] = _c[P[i]]
m = 31
vertex = list()
score = list()
vertex.append(P)
score.append(C)
for b in range(1, m + 1):
	p_bth = [0] * N
	c_bth = [0] * N
	for i in range(N):
		p_bth[i] = vertex[b - 1][vertex[b - 1][i]]
		c_bth[i] = score[b - 1][i] + score[b - 1][vertex[b - 1][i]]
	vertex.append(p_bth)
	score.append(c_bth)
MIN = -(1 << 63)
prv = [[MIN, 0] for _ in range(N)]
nxt = [[MIN, MIN] for _ in range(N)]
for b in range(m, -1, -1):
	for i in range(N):
		if K >> b & 1:
			nxt[vertex[b][i]][0] = max(nxt[vertex[b][i]][0], prv[i][0] + score[b][i])
			nxt[vertex[b][i]][1] = max(nxt[vertex[b][i]][1], prv[i][1] + score[b][i])
			nxt[i][0] = max(nxt[i][0], prv[i][0], prv[i][1])
		else:
			nxt[vertex[b][i]][0] = max(nxt[vertex[b][i]][0], prv[i][0] + score[b][i])
			nxt[i][0] = max(nxt[i][0], prv[i][0])
			nxt[i][1] = max(nxt[i][1], prv[i][1])
	(prv, nxt) = (nxt, prv)
ans = max((max(x) for x in prv))
if ans == 0:
	ans = max(C)
print(ans)


import numpy as np

def __starting_point():
	(N, K) = list(map(int, input().split()))
	P = [int(p) - 1 for p in input().split()]
	C = list(map(int, input().split()))
	cycleIDs = np.full(N, -1, np.int64)
	cycleInfs = []
	cycleID = 0
	procCnt = 0
	for n in range(N):
		v = n
		if cycleIDs[v] != -1:
			continue
		else:
			currentCycleCosts = []
			while True:
				currentCycleCosts.append(C[v])
				cycleIDs[v] = cycleID
				v = P[v]
				if cycleIDs[v] != -1:
					procCnt = K % len(currentCycleCosts)
					if len(currentCycleCosts) + procCnt <= K:
						procCnt += len(currentCycleCosts)
					cycleInfs.append((procCnt, len(currentCycleCosts), np.array(currentCycleCosts + currentCycleCosts)))
					cycleID += 1
					break
	ans = -10 ** 9
	for (procCnt, currentCycleSize, currentCycleCosts) in cycleInfs:
		loopScore = 0
		if np.sum(currentCycleCosts) > 0:
			cycleLoopCnt = (K - procCnt) // currentCycleSize
			loopScore = cycleLoopCnt * np.sum(currentCycleCosts[:currentCycleSize])
		for i in range(currentCycleSize):
			ans = max(ans, np.roll(currentCycleCosts, i).cumsum()[:procCnt].max() + loopScore)
	print(ans)
__starting_point()


(N, K) = map(int, input().split())
P = [int(p) for p in input().split()]
C = [int(c) for c in input().split()]
ans = max(C)
for i in range(N):
	used = [0] * N
	used[i] = 1
	loop = [C[i]]
	j = P[i] - 1
	while used[j] == 0:
		used[j] = 1
		loop.append(loop[-1] + C[j])
		j = P[j] - 1
	M = len(loop)
	if K >= M:
		if K % M == 0:
			t = 0
		else:
			t = max(loop[:K % M])
			t = max(t, 0)
		num = max(loop[-1] * (K // M) + t, max(loop), loop[-1] * (K // M - 1) + max(loop))
	else:
		num = max(loop[:K])
	ans = max(ans, num)
if max(C) <= 0:
	ans = max(C)
print(ans)


(N, K) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
K = K - 1
ans = -10 ** 9 - 1
for h in range(N):
	i = h + 1
	start = i
	circle = [c[i - 1]]
	i = p[i - 1]
	while i != start:
		score = circle[-1] + c[i - 1]
		circle.append(score)
		i = p[i - 1]
	l = len(circle)
	for j in range(min(l, K + 1)):
		if circle[l - 1] > 0:
			score = circle[j] + (K - j) // l * circle[l - 1]
		else:
			score = circle[j]
		ans = max(score, ans)
print(ans)


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
max_score = -float('inf')
for i in range(n):
	loop_score_array = []
	loop_score = 0
	loop_len = 0
	pos = i
	while True:
		pos = p[pos] - 1
		loop_score += c[pos]
		loop_score_array.append(loop_score)
		loop_len += 1
		if pos == i:
			break
	for (i, score) in enumerate(loop_score_array):
		if k - i - 1 < 0:
			continue
		loop_num = (k - i - 1) // loop_len
		score_sum = score + max(0, loop_score) * loop_num
		max_score = max(score_sum, max_score)
print(max_score)


(n, k) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
score_max = max(C)
for L in range(n):
	score = 0
	d = [0] * n
	r = 0
	d[L] = 1
	for _ in range(k):
		r += 1
		L = P[L] - 1
		score += C[L]
		score_max = max(score, score_max)
		if d[L] == 0:
			d[L] = 1
		elif score < 0:
			break
		else:
			roop = k // r - 1
			h = k % r + r
			score *= roop
			score_max = max(score, score_max)
			for _ in range(h):
				L = P[L] - 1
				score += C[L]
				score_max = max(score, score_max)
			break
print(score_max)


(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
best = max(C)
for i in range(N):
	curr = 0
	score = [0]
	start = i
	while P[start] != i:
		start = P[start]
		curr += C[start]
		score.append(curr)
	cycle_score = score[-1] + C[i]
	cycle_len = len(score)
	for j in range(cycle_len):
		if j <= K and j != 0:
			cycles = (K - j) // cycle_len
			thing = score[j] + max(0, cycle_score) * cycles
			best = max(best, thing)
		elif j == 0 and K >= cycle_len:
			thing = cycle_score * K // cycle_len
			best = max(best, thing)
print(best)


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)


f = lambda : [*map(int, input().split())]
(n, k) = f()
(p, c) = (f(), f())
p = [*map(lambda x: x - 1, p)]
a = -10 ** 9
for i in range(n):
	x = i
	l = []
	s = 0
	while 1:
		x = p[x]
		l += [c[x]]
		s += c[x]
		if x == i:
			break
	m = len(l)
	t = 0
	for j in range(m):
		if j + 1 > k:
			break
		t += l[j]
		a = max(a, t + (k - j - 1) // m * s * (s > 0))
print(a)


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


(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):
	cnt = 0
	k = 0
	done = set()
	S = []
	while i not in done:
		done.add(i)
		ni = P[i] - 1
		if len(S):
			S.append(S[-1] + C[ni])
		else:
			S.append(C[ni])
		i = ni
	if K <= len(S):
		score = max(S[:K])
	elif S[-1] <= 0:
		score = max(S)
	else:
		score1 = S[-1] * (K // len(S) - 1)
		score1 += max(S)
		score2 = S[-1] * (K // len(S))
		r = K % len(S)
		if r != 0:
			score2 += max(0, max(S[:r]))
		score = max(score1, score2)
	ans = max(ans, score)
print(ans)


(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = max(C)
for i in range(N):
	s = i
	l = [C[i]]
	while True:
		s = P[s]
		if s == i:
			break
		l.append(C[s])
	if sum(l) > 0:
		if K >= len(l):
			c = (K // len(l) - 1) * sum(l)
			n = K % len(l) + len(l)
		else:
			c = 0
			n = K
		ans = max(ans, c)
		s = i
		for j in range(n):
			c += C[s]
			s = P[s]
			ans = max(ans, c)
	n = min(N, K)
	s = i
	c = 0
	for j in range(n):
		c += C[s]
		s = P[s]
		ans = max(ans, c)
print(ans)


(N, K) = map(int, input().split())
P = [int(p) - 1 for p in input().split()]
C = list(map(int, input().split()))
max_score = -10 ** 9
for i in range(N):
	memo = set()
	score = 0
	cur = i
	move = 0
	while move < K and P[cur] not in memo:
		cur = P[cur]
		memo.add(cur)
		score += C[cur]
		move += 1
		max_score = max(score, max_score)
	if move < K and score > 0:
		score = max(K // move - 1, 1) * score
		move *= max(K // move - 1, 1)
		max_score = max(score, max_score)
		cur = i
		while move < K:
			cur = P[cur]
			score += C[cur]
			move += 1
			max_score = max(score, max_score)
print(max_score)


(n, k) = map(int, input().split())
(*p,) = map(int, input().split())
(*c,) = map(int, input().split())
ans = -10 ** 20
for i in range(n):
	loop = 1
	j = p[i] - 1
	acm = [c[j]]
	while j != i:
		j = p[j] - 1
		acm.append(acm[-1] + c[j])
		loop += 1
	if acm[-1] > 0:
		if k <= loop:
			cur = max(acm[:k])
		else:
			cur = k // loop * acm[-1]
			if k % loop > 0:
				cur = max(cur, cur + max(acm[:k % loop]))
			else:
				cur -= acm[-1]
				cur += max(acm)
	else:
		cur = max(acm[:min(k, loop)])
	ans = max(cur, ans)
print(ans)


(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 = -10 ** 18
for si in range(N):
	x = si
	loop = []
	total = 0
	while 1:
		x = P[x]
		loop.append(C[x])
		total += C[x]
		if x == si:
			break
	T = len(loop)
	tmp = 0
	for i in range(T):
		tmp += loop[i]
		if K < i + 1:
			break
		now = tmp
		if total > 0:
			loop_times = (K - (i + 1)) // T
			now += total * loop_times
		ans = max(ans, now)
print(ans)


(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
DP = [[C[P[n]]] for n in range(N)]
for start in range(N):
	visited = set()
	cur = P[start]
	while cur not in visited:
		visited.add(cur)
		cur = P[cur]
		DP[start].append(C[cur] + DP[start][-1])
for n in range(N):
	DP[n] = DP[n][:-1]
ans = -float('inf')
for start in range(N):
	for goal in range(min(K, len(DP[start]))):
		no_loop_sum = DP[start][goal]
		remain_hops = K - goal - 1
		if DP[start][-1] > 0:
			loops = remain_hops // len(DP[start])
		else:
			loops = 0
		ans = max(ans, no_loop_sum + DP[start][-1] * loops)
print(ans)


(N, K) = map(int, input().split())
P = [x - 1 for x in map(int, input().split())]
C = list(map(int, input().split()))
ans = -100000000000
for i in range(N):
	n = 0
	socre_sum = 0
	now = i
	while True:
		n += 1
		socre_sum += C[now]
		now = P[now]
		if i == now:
			break
	score = 0
	now = i
	for j in range(1, n + 1):
		score += C[now]
		now = P[now]
		if j > K:
			break
		ans = max(ans, score + max(0, socre_sum) * ((K - j) // n))
print(ans)


(N, K) = map(int, input().split())
P = [int(i) - 1 for i in input().split()]
Q = [int(i) for i in input().split()]
ans = -float('inf')
for i in range(N):
	now = i
	cnt = 0
	span = 0
	while True:
		span += 1
		cnt += Q[now]
		now = P[now]
		if now == i:
			break
	point = 0
	now = i
	for j in range(1, span + 1):
		point += Q[now]
		now = P[now]
		if j > K:
			break
		value = point + max(cnt, 0) * ((K - j) // span)
		ans = max(ans, value)
print(ans)


import sys, math

def calcweight_tree(N_vertices, edges, times, inf):
	distance = 0
	passed = [False] * N_vertices
	travel_max = -inf
	for i in range(N_vertices):
		if passed[i] == False:
			distance = 0
			left = i
			cost_sum = 0
			costs = []
			min_distance = inf
			while True:
				dest = edges[left][1]
				cost = edges[dest][0]
				if passed[dest] == False:
					passed[dest] = True
					cost_sum += cost
					costs.append(cost_sum)
					left = dest
					if min_distance > cost:
						min_distance = cost
				else:
					period = len(costs)
					increase_period = cost_sum
					break
			remainder = times % period
			cost_minus = [0]
			for j in range(period - 1):
				cost_minus.append(costs[j])
			if increase_period <= 0:
				costs_last = []
				remainder2 = remainder % period
				for j in range(period):
					costs_last.append(costs[j])
				for j in range(period):
					costs_last.append(costs_last[j] + increase_period)
				maxvalue = -inf
				for j in range(period):
					maxvalue_candidate = max(costs_last[j:j + period])
					if maxvalue_candidate - cost_minus[j] > maxvalue:
						maxvalue = maxvalue_candidate - cost_minus[j]
				travel_max = max(maxvalue, travel_max)
			else:
				costs_last = []
				remainder2 = remainder % period
				times_period = times // period - 1
				add_n = times_period * increase_period
				for j in range(remainder2, period):
					costs_last.append(costs[j] + add_n)
				for j in range(0, remainder2):
					costs_last.append(costs[j] + add_n + increase_period)
				for j in range(period):
					costs_last.append(costs_last[j] + increase_period)
				maxvalue = -inf
				for j in range(period):
					maxvalue_candidate = max(costs_last[j:j + period])
					if maxvalue_candidate - cost_minus[j] > maxvalue:
						maxvalue = maxvalue_candidate - cost_minus[j]
				travel_max = max(maxvalue, travel_max)
	return travel_max

def __starting_point():
	(N, K) = list(map(int, input().strip().split()))
	PList = list(map(int, input().strip().split()))
	CList = list(map(int, input().strip().split()))
	inf = 10 ** 10
	N_vertices = N
	edges3 = []
	costs = []
	for i in range(N):
		edges3.append([CList[i], PList[i] - 1])
	weight = calcweight_tree(N_vertices, edges3, K, inf)
	print(weight)
__starting_point()


(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 = -int(1e+18)
for si in range(n):
	x = si
	s = []
	opscore = 0
	while True:
		x = p[x]
		opscore += c[x]
		s.append(c[x])
		if x == si:
			break
	oplen = len(s)
	t = 0
	for i in range(oplen):
		t += s[i]
		if i + 1 > k:
			break
		now = t
		if opscore > 0:
			e = (k - (i + 1)) // oplen
			now += opscore * e
		ans = max(ans, now)
print(ans)


(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
if K <= N:
	ans = -10 ** 9
	for i in range(N):
		(now, last) = (i, 0)
		for _ in range(K):
			last += C[P[now]]
			ans = max(ans, last)
			now = P[now]
	print(ans)
	exit()
ans = -10 ** 9
for i in range(N):
	(tmp, now, done) = ([0], i, set())
	for _ in range(N + 1):
		tmp.append(tmp[-1] + C[P[now]])
		if P[now] == i:
			break
		now = P[now]
	tmp = tmp[1:]
	cnt = len(tmp)
	m = max(tmp)
	ans = max(ans, m, tmp[-1] * (K // cnt - 1) + m)
	if K % cnt != 0:
		ans = max(ans, tmp[-1] * (K // cnt) + max(tmp[:K % cnt]))
print(ans)


(n, k) = map(int, input().split())
p = [0] + list(map(int, input().split()))
c = [0] + list(map(int, input().split()))
ans = -10 ** 18
for i in range(1, n + 1):
	vis = set()
	now = i
	a = [0]
	m = k
	while m:
		vis.add(now)
		now = p[now]
		a += [c[now] + a[-1]]
		m -= 1
		if now in vis:
			break
	if m == 0 or a[-1] <= 0:
		cnt = max(a[1:])
	else:
		cnt = k // (k - m) * a[-1]
		if k % (k - m):
			cnt += max(a[1:k % (k - m) + 1])
		elif max(a[1:]) > a[-1]:
			cnt = cnt = (k // (k - m) - 1) * a[-1] + max(a[1:])
	ans = max(ans, cnt)
print(ans)


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


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -float('inf')
for s in range(N):
	S = []
	S.append(C[s])
	i = P[s] - 1
	while i != s:
		S.append(S[-1] + C[i])
		i = P[i] - 1
	if K <= len(S):
		score = max(S[:K])
	elif S[-1] <= 0:
		score = max(S)
	else:
		score1 = S[-1] * (K // len(S) - 1)
		score1 += max(S)
		score2 = S[-1] * (K // len(S))
		r = K % len(S)
		if r != 0:
			score2 += max(0, max(S[:r]))
		score = max(score1, score2)
	ans = max(ans, score)
print(ans)


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = -10 ** 9
for i in range(1, n + 1):
	m = i
	co = 0
	an = 0
	for j in range(n):
		m = p[m - 1]
		co += 1
		if m == i:
			break
	m = i
	x = [0 for j in range(2 * co)]
	for j in range(2 * co - 1):
		m = p[m - 1]
		x[j + 1] = x[j] + c[m - 1]
	if k <= co:
		ans = max(ans, max((x[j] for j in range(1, k + 1))))
	elif x[co] <= 0:
		ans = max(ans, max((x[j] for j in range(1, co + 1))))
	else:
		f = max(0, k // co - 1)
		an += x[co] * f
		s = k - f * co
		ans = max(ans, an + max((x[j] for j in range(1, s + 1))))
print(ans)


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


from itertools import accumulate
(N, K) = list(map(int, input().split()))
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = -10 ** 18 - 1
seen = [False] * N
for i in range(N):
	if seen[i]:
		continue
	loop = []
	now = i
	while seen[now] == False:
		seen[now] = True
		loop.append(C[now])
		now = P[now]
	loop_size = len(loop)
	loop_score = sum(loop)
	cumsum = list(accumulate(loop + loop))
	for j in range(1, min(K, loop_size) + 1):
		for l in range(loop_size):
			r = l + j
			subseq = cumsum[r] - cumsum[l]
			ans = max(ans, subseq, subseq + loop_score * ((K - j) // loop_size))
print(ans)


from collections import deque
it = lambda : list(map(int, input().strip().split()))

def maximise(L, R, cycle):
	cur = 0
	ans = max(cycle)
	queue = deque([0])
	dp = [0] * (2 * L + 1)
	for (i, num) in enumerate(cycle + cycle):
		j = i + 1
		cur += num
		while queue and j - queue[0] > R:
			queue.popleft()
		if queue:
			ans = max(ans, cur - dp[queue[0]])
		while queue and dp[queue[-1]] >= cur:
			queue.pop()
		queue.append(j)
		dp[j] = cur
	return ans

def get(K, cycle):
	L = len(cycle)
	T = sum(cycle)
	if K > L:
		B = (K - 1) // L
		R = K - B * L
	else:
		B = 0
		R = K
	return max(maximise(L, K, cycle), maximise(L, R, cycle) + max(0, B * T))

def solve():
	(N, K) = it()
	P = it()
	C = it()
	for i in range(N):
		P[i] -= 1
	cycles = []
	seen = [False] * N
	for i in range(N):
		if not seen[i]:
			cycle = []
			first = curr = i
			while True:
				seen[curr] = True
				cycle.append(C[curr])
				curr = P[curr]
				if curr == first:
					break
			cycles.append(cycle)
	ans = float('-inf')
	for cycle in cycles:
		ans = max(ans, get(K, cycle))
	return ans

def __starting_point():
	ans = solve()
	print(ans)
__starting_point()


import sys
readline = sys.stdin.buffer.readline

def even(n):
	return 1 if n % 2 == 0 else 0
(n, k) = map(int, readline().split())
p = list(map(int, readline().split()))
c = list(map(int, readline().split()))
p = [i - 1 for i in p]
ans = -10 ** 18
for i in range(n):
	lst1 = [c[i]]
	idx = p[i]
	while idx != i:
		lst1.append(c[idx])
		idx = p[idx]
	sm = sum(lst1)
	acc = 0
	for i in range(min(len(lst1), k + 2)):
		acc += lst1[i]
		a = acc
		if sm > 0:
			a += sm * ((k - (i + 1)) // len(lst1))
		ans = max(a, ans)
print(ans)


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


(n, k) = map(int, input().split())
next = list(map(int, input().split()))
next = list(map(lambda x: x - 1, next))
c = list(map(int, input().split()))
ans = -10 ** 17
for i in range(n):
	now = i
	cycle_sum = 0
	cycle_len = 0
	while True:
		cycle_sum += c[now]
		cycle_len += 1
		now = next[now]
		if now == i:
			break
	sum = 0
	cnt = 0
	while True:
		sum += c[now]
		cnt += 1
		if cnt > k:
			break
		laps = (k - cnt) // cycle_len
		score = sum + max(0, cycle_sum) * laps
		ans = max(ans, score)
		now = next[now]
		if now == i:
			break
print(ans)


import sys
(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 = -1e+18
for i in range(N):
	s = []
	total = 0
	x = i
	while True:
		x = P[x]
		total += C[x]
		s.append(C[x])
		if x == i:
			break
	l = len(s)
	t = 0
	for j in range(l):
		t += s[j]
		if j + 1 > K:
			break
		now = t
		if total > 0:
			e = (K - (j + 1)) // l
			now += total * e
		ans = max(ans, now)
print(ans)


(n, k) = map(int, input().split())
P = [int(x) - 1 for x in input().split()]
C = [int(x) for x in input().split()]
vis = [0 for i in range(n + 1)]
res = -10000000000000000000000
for i in range(0, n):
	if vis[i] == 0:
		su = 0
		vis[i] = 1
		v = []
		v.append(C[i])
		su += C[i]
		x = P[i]
		while x != i:
			vis[x] = 1
			su += C[x]
			v.append(C[x])
			x = P[x]
		vs = len(v)
		for ii in range(vs):
			umm = 0
			for j in range(vs):
				x = (ii + j) % vs
				umm += v[x]
				steps = 1 + (x - ii + vs) % vs
				if k >= vs:
					if su > 0:
						r = max((k - steps) // vs, 0)
						res = max(res, r * su + umm)
					else:
						res = max(res, umm)
				elif steps <= k:
					res = max(res, umm)
print(res)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -99999999999999
for i in range(N):
	x = i
	total = 0
	s = []
	while 1:
		x = P[x] - 1
		s.append(C[x])
		total += C[x]
		if x == i:
			break
	l = len(s)
	t = 0
	for i in range(l):
		t += s[i]
		if i + 1 > K:
			break
		now = t
		if total > 0:
			cycle = int((K - i - 1) / l)
			now += total * cycle
		ans = max(ans, now)
print(ans)


(N, K) = map(int, input().split())
P = [int(t) - 1 for t in input().split()]
C = list(map(int, input().split()))
ans = -1e+18
for si in range(N):
	x = si
	s = []
	tot = 0
	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
		if ans < now:
			ans = now
print(ans)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = []
for u in range(N):
	v = P[u] - 1
	cnt = C[v]
	val = cnt
	jump = 1
	while v != u and jump < K:
		v = P[v] - 1
		cnt += C[v]
		val = max(val, cnt)
		jump += 1
	if jump < K:
		res = max(0, K // jump - 2)
		cnt += cnt * res
		val = max(val, cnt)
		jump += jump * res
	while jump < K:
		v = P[v] - 1
		cnt += C[v]
		val = max(val, cnt)
		jump += 1
	ans.append(val)
print(max(ans))


def nasu(s):
	x = s
	ma = MC
	su = 0
	L = []
	for i in range(K):
		x = P[x] - 1
		su += C[x]
		L.append(C[x])
		ma = max(ma, su)
		if x == s:
			break
	else:
		return ma
	if su <= 0:
		return ma
	n = i + 1
	(div, mod) = divmod(K, n)
	ans = (div - 1) * su + ma
	da = div * su
	for i in range(mod):
		da += L[i]
		ans = max(ans, da)
	return ans
(N, K) = list(map(int, input().split()))
P = list(map(int, input().split()))
C = list(map(int, input().split()))
MC = min(C)
ans = MC
for i in range(N):
	ans = max(ans, nasu(i))
print(ans)


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = -float('inf')
for s in range(N):
	c = 0
	i = P[s]
	score = C[i]
	ans = max(ans, score)
	c += 1
	while i != s and c < K:
		i = P[i]
		score += C[i]
		ans = max(ans, score)
		c += 1
	if c == K or score <= 0:
		continue
	q = K // c
	score *= q - 1
	c *= q - 1
	while c < K:
		i = P[i]
		score += C[i]
		ans = max(ans, score)
		c += 1
print(ans)


(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = -float('inf')
for start in range(N):
	cur = P[start]
	scores = [C[cur]]
	for _ in range(K):
		if cur == start:
			break
		cur = P[cur]
		scores.append(C[cur] + scores[-1])
	for goal in range(len(scores)):
		no_loop_sum = scores[goal]
		remain_hops = K - goal - 1
		if scores[-1] > 0:
			loops = remain_hops // len(scores)
		else:
			loops = 0
		ans = max(ans, no_loop_sum + scores[-1] * loops)
print(ans)


import sys
input = sys.stdin.readline

def main():
	(n, k) = list(map(int, input().split()))
	p = [int(x) - 1 for x in input().split()]
	c = list(map(int, input().split()))
	doubling = [[0] * n for i in range(31)]
	doubling_max = [[0] * n for i in range(31)]
	place = [[0] * n for i in range(31)]
	ans = -1000000000
	for i in range(n):
		sub = c[p[i]]
		if sub >= 0:
			break
		if ans < sub:
			ans = sub
		if i == n - 1:
			print(ans)
			return
	for i in range(31):
		if i == 0:
			for j in range(n):
				doubling[i][j] = c[p[j]]
				place[i][j] = p[j]
			continue
		for j in range(n):
			place[i][j] = place[i - 1][place[i - 1][j]]
			doubling[i][j] = doubling[i - 1][j] + doubling[i - 1][place[i - 1][j]]
	for i in range(31):
		if i == 0:
			for j in range(n):
				doubling_max[i][j] = doubling[i][j]
			continue
		for j in range(n):
			doubling_max[i][j] = max(doubling_max[i - 1][j], doubling[i - 1][j] + doubling_max[i - 1][place[i - 1][j]])
	ans = 0
	judge = []
	key = 0
	while k:
		if k % 2:
			judge.append(key)
		k //= 2
		key += 1
	judge.reverse()
	for i in range(n):
		pl = i
		key = 0
		for j in range(len(judge)):
			if ans < key + doubling_max[judge[j]][pl]:
				ans = key + doubling_max[judge[j]][pl]
			key += doubling[judge[j]][pl]
			pl = place[judge[j]][pl]
	print(ans)

def __starting_point():
	main()
__starting_point()


(N, K) = map(int, input().split())
(*P,) = map(int, input().split())
(*C,) = map(int, input().split())
ans = -float('inf')
for pos in range(N):
	used = [-1] * N
	cost = [0] * (N + 1)
	for k in range(N + 1):
		if k:
			cost[k] = cost[k - 1] + C[pos]
		if used[pos] >= 0:
			loop_size = k - used[pos]
			break
		used[pos] = k
		pos = P[pos] - 1
	if cost[loop_size] <= 0:
		ans = max(ans, max(cost[1:K + 1]))
	else:
		(a, b) = divmod(K, loop_size)
		v1 = cost[loop_size] * (a - 1) + max(cost[:K + 1])
		v2 = cost[loop_size] * a + max(cost[:b + 1])
		ans = max(ans, max(v1, v2) if a else v2)
print(ans)


(N, K) = map(int, input().split())
(*P,) = map(int, input().split())
(*C,) = map(int, input().split())
d = [[0] * N for _ in [0] * N]
l = [0] * N
for i in range(N):
	j = i
	cnt = 0
	while True:
		prev_j = j
		j = P[j] - 1
		d[i][j] = d[i][prev_j] + C[j]
		cnt += 1
		if j == i:
			break
	l[i] = cnt
ans = -10 ** 10
for i in range(N):
	n = (K - N) // l[i]
	tmp = max(0, d[i][i]) * n
	k = K - n * l[i]
	j = i
	for _ in range(2 * N):
		if k <= 0:
			break
		k -= 1
		tmp += C[j]
		j = P[j] - 1
		ans = max(ans, tmp)
print(ans)


from numba import jit

@jit
def main():
	(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):
		(start, count) = (i, 1)
		val = c[start]
		while p[start] - 1 != i:
			start = p[start] - 1
			count += 1
			val += c[start]
		start = i
		if val > 0:
			a = (k // count - 1) * val
			ans = max(a, ans)
			num = count + k % count
		else:
			a = 0
			num = min(k, count)
		for _ in range(num):
			a += c[start]
			start = p[start] - 1
			ans = max(a, ans)
	print(ans)
main()


from collections import defaultdict
from collections import deque
from collections import Counter
import math

def readInt():
	return int(input())

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

def readChar():
	return input()

def readChars():
	return input().split()
(n, k) = readInts()
p = [0] + readInts()
c = [0] + readInts()
ans = -1 * float('inf')
for i in range(1, n + 1):
	j = p[i]
	t = [0]
	al = set()
	while j not in al:
		t.append(t[-1] + c[j])
		al.add(j)
		j = p[j]
	if t[-1] <= 0:
		ans = max(ans, max(t[1:k + 1]))
	else:
		kuri = (k - 1) // (len(t) - 1)
		s = kuri * t[-1]
		re = k - kuri * (len(t) - 1)
		ans = max(ans, max(s, s + max(t[:re + 1])))
print(ans)


from itertools import accumulate

def main():
	(n, k) = list(map(int, input().split()))
	P = [int(x) - 1 for x in input().split()]
	C = [int(x) for x in input().split()]
	F = [False] * n
	a = -10 ** 9
	for i in range(n):
		if F[i]:
			continue
		(p, F[i], L) = (i, True, [C[i]])
		while P[p] != i:
			p = P[p]
			F[p] = True
			L.append(C[p])
		(t, l) = (sum(L), len(L))
		s = t * (k // l - 1) if t > 0 else 0
		(m, L) = (-10 ** 9, L * 3)
		u = k % l + l if t > 0 else min(k, l)
		for j in range(l):
			m = max(m, max(accumulate(L[j:j + u])))
		a = max(s + m, a)
	print(a)
main()


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)


import numpy as np
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
(cycles, check) = ([], [False] * n)
for pi in p:
	if not check[pi - 1]:
		(curr, cycle) = (pi, [])
		check[pi - 1] = True
		while pi != p[curr - 1]:
			check[curr - 1] = True
			cycle.append(c[curr - 1])
			curr = p[curr - 1]
		check[curr - 1] = True
		cycles.append(cycle + [c[curr - 1]])
scores = []
for cycle in (np.array(cycle) for cycle in cycles):
	for i in range(cycle.size):
		cum = np.roll(cycle, i).cumsum()
		if cum[-1] > 0 and k > cycle.size:
			scores.append(cum[-1] * (k // cycle.size - 1) + np.concatenate([cum, cum[:k % cycle.size] + cum[-1]]).max())
		else:
			scores.append(cum[:min(k, cum.size)].max())
print(max(scores))


import sys
sys.setrecursionlimit(50000)
(N, K) = [int(v) for v in input().split()]
P = [int(v) - 1 for v in input().split()]
C = [int(v) for v in input().split()]
visited = [True for _ in range(N)]
cycle = []
ans = -float('inf')
for sn in range(N):
	cost = []
	nn = sn
	while True:
		cost.append(C[nn])
		nn = P[nn]
		if sn == nn:
			break
	total = sum(cost)
	l = len(cost)
	t = 0
	for i in range(l):
		t += cost[i]
		if i + 1 > K:
			break
		now = t
		if total > 0:
			e = (K - i - 1) // l
			now += total * e
		ans = max(ans, now)
print(int(ans))


(n, k) = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
c = list(map(int, input().split()))
ans = max(c)
if ans <= 0:
	print(ans)
	exit()
for i in range(n):
	now = i
	score = [0]
	while p[now] != i:
		now = p[now]
		score.append(score[-1] + c[now])
	cyc_score = score[-1] + c[i]
	cyc = len(score)
	max_loop = k // cyc
	if cyc_score <= 0:
		tmp = max(score[:min(k + 1, cyc)])
	else:
		tmp = max(score) + (max_loop - 1) * cyc_score
		tmp = max(tmp, max(score[:k % cyc + 1]) + max_loop * cyc_score)
	ans = max(ans, tmp)
print(ans)


from itertools import accumulate
(N, K) = list(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)]))
			elif 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)


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


(n, k) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
D = [-1] * n
ans = -float('inf')
for (i, p) in enumerate(P):
	ans = max(ans, C[p])
	temp = p
	res = C[p]
	cnt = 1
	while temp != i and cnt < k:
		temp = P[temp]
		res += C[temp]
		cnt += 1
		ans = max(ans, res)
	D[i] = (cnt, res)
for i in range(n):
	(a, b) = D[i]
	ans = max(ans, b)
	if a == k:
		continue
	if b < 0:
		continue
	temp = b * (k // a - 1)
	rest = k % a + a
	now = i
	for _ in range(rest):
		now = P[now]
		temp += C[now]
		ans = max(ans, temp)
print(ans)


(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()))
reach = [False] * n
x = []
for i in range(n):
	if reach[i]:
		continue
	buf = []
	cur = i
	while not reach[cur]:
		buf.append(c[cur])
		reach[cur] = True
		cur = p[cur]
	x.append(buf)
ans = max(c)
import itertools
for i in x:
	n = k // len(i)
	ind = k % len(i)
	if n > 0:
		n -= 1
		ind += len(i)
	else:
		ind = min(k, len(i) * 2)
	ii = i + i + i
	r = list(itertools.accumulate(ii))
	a = max(0, r[len(i) - 1] * n)
	for j in range(len(i)):
		for z in range(1, ind + 1):
			s = r[j + z] - r[j]
			ans = max(ans, a + s)
print(ans)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
a = []
ans = -10 ** 10
for i in range(N):
	idx = P[i] - 1
	z = set()
	rl = []
	c = 0
	tc = 0
	while idx not in z and c < K:
		tc += C[idx]
		rl.append(tc)
		ans = max(ans, tc)
		z.add(idx)
		idx = P[idx] - 1
		c += 1
	if c < K:
		(d, m) = divmod(K, c)
		if m == 0:
			d -= 1
			m = c
		tc = d * tc
		tc += max(rl[:m])
		ans = max(ans, tc)
print(ans)


from itertools import accumulate
(N, K, *PC) = map(int, open(0).read().split())
(P, C) = ([0] + PC[:N], [0] + PC[N:])
ans = float('-inf')
for start in range(1, N + 1):
	path = []
	cur = P[start]
	path = [C[start]]
	while cur != start:
		path.append(C[cur])
		cur = P[cur]
	A = list(accumulate(path))
	(q, r) = divmod(K, len(path))
	res = 0
	if A[-1] >= 0:
		if r == 0:
			q -= 1
			r += len(path)
		res += A[-1] * q
	elif q >= 1:
		r = len(path)
	ans = max(ans, res + max(A[:r]))
print(ans)


(N, K) = [int(x) for x in input().split()]
P = [0] + [int(x) for x in input().split()]
C = [0] + [int(x) for x in input().split()]
max_score = max(C[1:])
for init in range(1, N + 1):
	score = [0]
	i = init
	for k in range(1, K + 1):
		i = P[i]
		score.append(score[-1] + C[i])
		max_score = max(max_score, score[k])
		if i == init:
			loop_score = score[-1]
			loop_len = k
			if loop_score > 0:
				max_score = max(max_score, max((score[j] + loop_score * ((K - j) // loop_len) for j in range(1, loop_len + 1))))
			break
print(max_score)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -1 * float('inf')
for i in range(N):
	k = i
	Cc = []
	Ct = 0
	while 1:
		k = P[k] - 1
		Cc.append(C[k])
		if i == k:
			break
	l = len(Cc)
	Ct = sum(Cc)
	t = 0
	for j in range(l):
		t += Cc[j]
		if j >= K:
			break
		now = t
		if Ct > 0:
			e = (K - j - 1) // l
			now += Ct * e
		ans = max(ans, now)
print(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):
	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)


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

def check(start):
	global k
	i = start
	cnt = 0
	score = 0
	cand = []
	while True:
		i = p[i] - 1
		score += c[i]
		cand.append(score)
		cnt += 1
		if i == start:
			break
	res = -10 ** 10
	if score >= 0:
		for (j, candj) in enumerate(cand):
			if k - j - 1 >= 0:
				res = max(res, (k - j - 1) // cnt * score + candj)
	else:
		for (j, candj) in enumerate(cand):
			if k - j - 1 >= 0:
				res = max(res, candj)
	return res
ans = -10 ** 10
for i in range(n):
	ans = max(ans, check(i))
print(ans)


import sys
input = sys.stdin.readline
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -float('inf')
for s in range(N):
	S = []
	i = P[s] - 1
	S.append(C[i])
	while i != s:
		i = P[i] - 1
		S.append(S[-1] + C[i])
	if K <= len(S):
		tmp = max(S[:K])
	elif S[-1] <= 0:
		tmp = max(S)
	else:
		tmp1 = S[-1] * (K // len(S) - 1)
		tmp1 += max(S)
		tmp2 = S[-1] * (K // len(S))
		r = K % len(S)
		if r != 0:
			tmp2 += max(0, max(S[:r]))
		tmp = max(tmp1, tmp2)
	ans = max(ans, tmp)
print(ans)


(N, K) = map(int, input().split())
moves = [0] + list(map(int, input().split()))
points = [0] + list(map(int, input().split()))
INF = 10 ** 10
answer = -INF
for start in range(1, N + 1):
	circle = [start]
	next = moves[start]
	c_score = points[start]
	while next != start:
		circle.append(next)
		c_score += points[next]
		next = moves[next]
	m_score = 0
	for i in range(min(len(circle), K)):
		m_score += points[circle[i]]
		loop_cnt = (K - i - 1) // len(circle)
		answer = max(answer, m_score + max(0, loop_cnt * c_score))
print(answer)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
answer = max(C)
for i in range(N):
	pos = P[i] - 1
	score = C[pos]
	score_list = [score]
	step = 1
	while pos != i and step < K:
		pos = P[pos] - 1
		score += C[pos]
		score_list.append(score)
		step += 1
	score_max = max(score_list)
	if score_list[-1] > 0 and step < K:
		loop = K // step
		amari = K % step
		for j in range(step):
			if j < amari:
				score_max = max(score_max, score_list[-1] * loop + score_list[j])
			else:
				score_max = max(score_max, score_list[-1] * (loop - 1) + score_list[j])
	answer = max(answer, score_max)
print(answer)


(N, K) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = -1 * 10 ** 9
for si in range(N):
	x = si
	total = 0
	l = 0
	s = list()
	while 1:
		x = p[x] - 1
		s.append(c[x])
		l += 1
		total += c[x]
		if x == si:
			break
	t = 0
	for i in range(l):
		now = 0
		if i + 1 > K:
			break
		t += s[i]
		now += t
		if total > 0:
			e = (K - (i + 1)) // l
			now += total * e
		ans = max(ans, now)
print(ans)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
dummy = set()
loop = []
X = set(range(N))
while len(dummy) != N:
	a = []
	k = min(X - dummy)
	a.append(k)
	dummy.add(k)
	l = P[k] - 1
	while l != k:
		a.append(l)
		dummy.add(l)
		l = P[l] - 1
	loop.append(a)
ans = -10 ** 300
for l in loop:
	temp = 0
	s = len(l)
	ssum = 0
	k = 0
	for i in range(s):
		ssum += C[l[i]]
	if ssum > 0:
		temp += (K - 1) // s * ssum
		k = K - (K - 1) // s * s
	else:
		k = min(K, s)
	kmax = -10 ** 300
	for ii in range(s):
		tempscore = temp
		for jj in range(1, k + 1):
			tempscore += C[l[(ii + jj) % s]]
			if tempscore > kmax:
				kmax = tempscore
	if kmax > ans:
		ans = kmax
print(ans)


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


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
_c = list(map(int, input().split()))
c = [0] * n
for i in range(n):
	p[i] -= 1
	c[i] = _c[p[i]]
m = 31
MIN = -(1 << 63)
vertex = list()
score = list()
vertex.append(p)
score.append(c)
for a in range(1, m + 1):
	p_ath = [0] * n
	c_ath = [0] * n
	for i in range(n):
		p_ath[i] = vertex[a - 1][vertex[a - 1][i]]
		c_ath[i] = score[a - 1][i] + score[a - 1][vertex[a - 1][i]]
	vertex.append(p_ath)
	score.append(c_ath)
prv = [[MIN, 0] for _ in range(n)]
nxt = [[MIN, MIN] for _ in range(n)]
for b in range(m, -1, -1):
	for i in range(n):
		if k >> b & 1:
			nxt[vertex[b][i]][0] = max(nxt[vertex[b][i]][0], prv[i][0] + score[b][i])
			nxt[vertex[b][i]][1] = max(nxt[vertex[b][i]][1], prv[i][1] + score[b][i])
			nxt[i][0] = max(nxt[i][0], prv[i][0], prv[i][1])
		else:
			nxt[vertex[b][i]][0] = max(nxt[vertex[b][i]][0], prv[i][0] + score[b][i])
			nxt[i][0] = max(nxt[i][0], prv[i][0])
			nxt[i][1] = max(nxt[i][1], prv[i][1])
	(prv, nxt) = (nxt, prv)
ans = max((max(x) for x in prv))
if ans == 0:
	ans = max(c)
print(ans)


import sys

class SWAG:

	def __init__(self):
		self.fold_l = []
		self.r = []
		self.fold_r = ~(1 << 60)

	def push(self, a):
		if self.fold_r < a:
			self.fold_r = a
		self.r.append(a)

	def pop(self):
		if not self.fold_l:
			self.r.reverse()
			self.fold_l = self.r
			self.r = []
			self.fold_r = ~(1 << 60)
			fold_l = self.fold_l
			for i in range(len(fold_l) - 1):
				if fold_l[i + 1] < fold_l[i]:
					fold_l[i + 1] = fold_l[i]
		self.fold_l.pop()

	def get(self):
		if not self.fold_l:
			return self.fold_r
		elif not self.r:
			return self.fold_l[-1]
		else:
			return max(self.fold_l[-1], self.fold_r)
(n, k) = list(map(int, input().split()))
p = [*list(map(int, input().split()))]
c = [*list(map(int, input().split()))]
for i in range(n):
	p[i] -= 1
if max(c) < 0:
	print(max(c))
	return
ans = 0
used = [False] * n
for i in range(n):
	if used[i]:
		continue
	loop = []
	at = i
	while not used[at]:
		loop.append(c[at])
		used[at] = True
		at = p[at]
	siz = len(loop)
	cusum = [0] + loop * 3
	for i in range(siz * 3):
		cusum[i + 1] += cusum[i]
	sum = max(0, cusum[siz])
	d = k % siz
	swag = SWAG()
	for i in range(d):
		swag.push(cusum[i])
	for i in range(siz):
		swag.push(cusum[d + i])
		ans = max(ans, swag.get() - cusum[i] + sum * (k // siz))
		swag.pop()
	if k < siz:
		continue
	d = k % siz + siz
	swag = SWAG()
	for i in range(d):
		swag.push(cusum[i])
	for i in range(siz):
		swag.push(cusum[d + i])
		ans = max(ans, swag.get() - cusum[i] + sum * (k // siz - 1))
		swag.pop()
print(ans)


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


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
g = []
for i in range(n):
	ans = c[i]
	e = [ans]
	f = i
	a = 1
	while a < k:
		i = p[i] - 1
		if i == f:
			break
		a += 1
		ans += c[i]
		e.append(ans)
	if e[-1] > 0 and a < k:
		w = k % len(e)
		if w != 0:
			y = k // len(e) * e[-1] + max(e[:w])
		else:
			y = (k // len(e) - 1) * e[-1] + max(e)
		g.append(y)
	else:
		g.append(max(e))
print(max(g))


(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
INF = 10 ** 18
ans = -INF
for i in range(N):
	arr = []
	tot = 0
	cnt = 0
	nex = i
	while cnt < K:
		nex = P[nex]
		tot += C[nex]
		arr.append(tot)
		cnt += 1
		if nex == i:
			break
	if cnt < K:
		cycle = cnt
		cycle_score = tot
		(loop, amari) = (K // cycle, K % cycle)
		for j in range(cycle):
			if j < amari:
				arr.append(cycle_score * loop + arr[j])
			else:
				arr.append(cycle_score * (loop - 1) + arr[j])
	ans = max(ans, max(arr))
print(ans)


(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):
	now = i
	cnt = [0]
	for j in range(n):
		nxt = p[now]
		cnt.append(cnt[j] + c[nxt])
		now = nxt
		if now == i:
			break
	m = len(cnt) - 1
	if k <= m:
		s = max(cnt[1:k + 1])
	elif cnt[-1] < 0:
		s = max(cnt[1:])
	else:
		t = k // m
		s = (t - 1) * cnt[-1] + max(cnt[1:])
		s = max(s, t * cnt[-1] + max(cnt[:k - t * m + 1]))
	ans = max(ans, s)
print(ans)


(N, K) = map(int, input().split())
P = [int(a) - 1 for a in input().split()]
C = [int(a) for a in input().split()]
ma = -10 ** 10
for i in range(N):
	l = 1
	j = P[i]
	s = C[j]
	ma = max(ma, s)
	while j != i:
		j = P[j]
		s += C[j]
		l += 1
		if K >= l:
			ma = max(ma, s)
	c = 1
	j = P[j]
	t = C[j]
	if K >= c:
		ma = max(ma, t + (K - c) // l * s)
	while j != i:
		j = P[j]
		t += C[j]
		c += 1
		if K >= c:
			ma = max(ma, t + (K - c) // l * s)
print(ma)


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
for i in range(n):
	p[i] -= 1
ans = -12345678901234567
for st in range(n):
	score = 0
	now = st
	for i in range(1, k + 1):
		now = p[now]
		score += c[now]
		ans = max(ans, score)
		if now == st:
			cnt = k // i - 1
			if cnt > 1:
				score *= cnt
				i *= cnt
				ans = max(ans, score)
			break
	for j in range(i + 1, k + 1):
		now = p[now]
		score += c[now]
		ans = max(ans, score)
print(ans)


(n, k) = map(int, input().split())
p = [int(pi) - 1 for pi in input().split()]
c = list(map(int, input().split()))
A = max(c)
seen = [False] * n
for i in range(n):
	if seen[i]:
		continue
	ids = []
	ccost = 0
	while not seen[i]:
		ccost += c[i]
		ids.append(i)
		seen[i] = True
		i = p[i]
	cn = len(ids)
	(ccnt, m) = divmod(k, cn)
	if ccnt > 0:
		ccnt -= 1
		m += cn
	ans = max((c[i] for i in ids))
	for s in ids:
		so = s
		now = 0
		for _ in range(m):
			s = p[s]
			now += c[s]
			ans = max(now, ans)
	if ccost > 0:
		ans += ccnt * ccost
	A = max(A, ans)
print(A)


from numba import njit
from sys import maxsize

@njit
def solve(n, k, p, c):
	used = [0] * n
	ss = []
	for i in range(n):
		if used[i]:
			continue
		now = i
		s = []
		while not used[now]:
			used[now] = 1
			s.append(c[now])
			now = p[now]
		ss.append(s)
	res = -maxsize
	for s in ss:
		s_len = len(s)
		cumsum = [0]
		for i in range(2 * s_len):
			cumsum.append(cumsum[-1] + s[i % s_len])
		max_sum = [-maxsize] * s_len
		for i in range(s_len):
			for j in range(s_len):
				max_sum[j] = max(max_sum[j], cumsum[i + j] - cumsum[i])
		for i in range(s_len):
			if i > k:
				continue
			v = (k - i) // s_len
			if i == 0 and v == 0:
				continue
			if cumsum[s_len] > 0:
				res = max(res, max_sum[i] + cumsum[s_len] * v)
			elif i > 0:
				res = max(res, max_sum[i])
	print(res)

def __starting_point():
	(n, k) = list(map(int, input().split()))
	p = list([int(x) - 1 for x in input().split()])
	c = list(map(int, input().split()))
	solve(n, k, p, c)
__starting_point()


(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):
	start = i
	next_ = start
	loop_score = 0
	loop_count = 0
	while True:
		loop_count += 1
		loop_score += C[next_]
		next_ = P[next_]
		if next_ == start:
			break
	in_score = 0
	in_count = 0
	for k in range(K):
		in_count += 1
		in_score += C[next_]
		loop_num = (K - in_count) // loop_count
		score = in_score + max(0, loop_score) * loop_num
		ans = max(ans, score)
		next_ = P[next_]
		if next_ == start:
			break
print(ans)


(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
maxscore = -10 ** 18
for st in range(N):
	cumsum = [0]
	now = st
	while P[now] != st:
		now = P[now]
		cumsum.append(cumsum[-1] + C[now])
	cumsum.append(cumsum[-1] + C[st])
	m = len(cumsum) - 1
	loopsum = cumsum[-1]
	if loopsum < 0:
		maxscore = max(maxscore, max(cumsum[1:min(K + 1, m + 1)]))
		continue
	score = (K // m - 1) * loopsum
	extended_cumsum = cumsum + [cumsum[i] + loopsum for i in range(1, K % m + 1)]
	score += max(extended_cumsum)
	maxscore = max(maxscore, score)
print(maxscore)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -1000000000
for i in range(N):
	cost = 0
	S = []
	x = P[i] - 1
	l = 1
	while 1:
		cost += C[x]
		S.append(cost)
		if x == i:
			break
		l += 1
		x = P[x] - 1
	if cost > 0:
		for j in range(l):
			ans = max(ans, S[j] + cost * ((K - j - 1) // l))
	else:
		ans = max(ans, max(S[:min(K, l)]))
print(ans)


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

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


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


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
ans = -10 ** 18
for start in range(N):
	now = start
	cycle = [0]
	while True:
		now = P[now] - 1
		cycle.append(cycle[-1] + C[now])
		if now == start:
			break
	L = len(cycle) - 1
	if cycle[-1] < 0 or K <= L:
		score = max(cycle[1:min(L + 1, K) + 1])
	else:
		score1 = cycle[-1] * (K // L) + max(cycle[:K % L + 1])
		score2 = cycle[-1] * (K // L - 1) + max(cycle)
		score = max(score1, score2)
	ans = max(ans, score)
print(ans)


(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = -float('inf')
for i in range(N):
	visited = set()
	tmp = 0
	for k in range(K):
		if P[i] in visited:
			break
		tmp += C[P[i]]
		i = P[i]
		visited.add(i)
		ans = max(ans, tmp)
	if tmp < 0:
		continue
	l = len(visited)
	rem = K - l
	(d, m) = divmod(rem, l)
	if m == 0 and d > 0:
		m = l
		d -= 1
	tmp *= d + 1
	for k in range(m):
		tmp += C[P[i]]
		i = P[i]
		ans = max(ans, tmp)
print(ans)


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
result = -float('inf')
for i in range(N):
	p = P[i] - 1
	c = C[p]
	k = K - 1
	t = c
	while p != i and k != 0:
		p = P[p] - 1
		c += C[p]
		t = max(t, c)
		k -= 1
	if k == 0 or c <= 0:
		result = max(result, t)
		continue
	l = K - k
	c = c * (K // l - 1)
	k = K - (K // l - 1) * l
	t = c
	while k != 0:
		p = P[p] - 1
		c += C[p]
		t = max(t, c)
		k -= 1
	result = max(result, t)
print(result)


def solve(n, x, k):
	ans = -10 ** 20
	s = 0
	sx = sum(x)
	for i in range(n):
		if i + 1 > k:
			break
		s += x[i]
		d = (k - i - 1) // n * sx
		ans = max(ans, s + d, s)
	return ans
(n, k) = map(int, input().split())
p = list(map(lambda x: int(x) - 1, input().split()))
c = list(map(int, input().split()))
ans = -10 ** 20
for i in range(n):
	x = [c[i]]
	j = p[i]
	while i != j:
		x.append(c[j])
		j = p[j]
	x = x[1:] + [x[0]]
	ans = max(ans, solve(len(x), x, k))
print(ans)


(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = -float('inf')
for st in range(N):
	S = []
	temp = P[st]
	S.append(C[temp])
	while temp != st:
		temp = P[temp]
		S.append(S[-1] + C[temp])
	cnt = len(S)
	(loop, k) = divmod(K, cnt)
	point = 0
	if S[-1] >= 0:
		if k == 0:
			loop -= 1
			k += cnt
		point += S[-1] * loop
	elif loop >= 1:
		k = cnt
	ans = max(ans, point + max(S[:k]))
print(ans)


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


(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 si in range(n):
	x = si
	S = []
	tot = 0
	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):
		if i + 1 > k:
			break
		t += S[i]
		now = t
		if tot > 0:
			e = (k - (i + 1)) // l
			now += tot * e
		ans = max(ans, now)
print(ans)


def main():
	(N, K) = map(int, input().split())
	P = list(map(lambda x: int(x) - 1, input().split()))
	C = list(map(int, input().split()))
	S = 0
	M = C[0]
	for s in range(N):
		t = 0
		p = s
		m = C[s]
		i = 0
		skipped = False
		while i < K:
			t += C[p]
			p = P[p]
			i += 1
			m = max(m, t)
			if p == s and (not skipped):
				if t <= 0:
					break
				skipped = True
				skip = K // i - 2
				if skip < 1:
					continue
				t += t * skip
				m = max(m, t)
				i += i * skip
		M = max(M, m)
	return M
print(main())


def resolve():
	(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 = -1e+18
	for i in range(N):
		n = P[i]
		score = C[n]
		t = [score]
		while n != i:
			n = P[n]
			score += C[n]
			t.append(score)
		total = t[-1]
		l = len(t)
		for i in range(min(K, l)):
			temp_score = t[i]
			if total > 0 and K > l:
				e = int((K - (i + 1)) / l)
				temp_score += total * e
			ans = max(ans, temp_score)
	print(ans)
resolve()


(n, k) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = -10 ** 18
for i in range(n):
	x = i
	sc = []
	tot = 0
	while True:
		x = P[x]
		sc.append(C[x])
		tot += C[x]
		if x == i:
			break
	l = len(sc)
	cum = 0
	for j in range(l):
		cum += sc[j]
		if j + 1 > k:
			break
		val = cum
		if tot > 0:
			cyc = (k - (j + 1)) // l
			val += tot * cyc
		ans = max(ans, val)
print(ans)


(N, K) = map(int, input().split())
P = list(map(lambda x: int(x) - 1, input().split()))
C = list(map(int, input().split()))
ans = -10 ** 18
for si in range(N):
	x = si
	score = []
	total = 0
	while True:
		x = P[x]
		score.append(C[x])
		total += C[x]
		if x == si:
			break
	l = len(score)
	t = 0
	for i in range(l):
		t += score[i]
		if i + 1 > K:
			break
		now = t
		if total > 0:
			e = (K - i - 1) // l
			now += total * e
		ans = max(ans, now)
print(ans)


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
c_list = []
rink_list = []
visited = set()
ans = -10 ** 10
for i in range(n):
	sum_c = c[i]
	j = p[i] - 1
	num = 1
	while i != j:
		sum_c += c[j]
		j = p[j] - 1
		num += 1
	sum_c = max(0, sum_c)
	cnt = 1
	j = p[i] - 1
	tmp = c[i]
	ans = max(ans, tmp + sum_c * ((k - cnt) // num))
	while cnt < k and i != j:
		cnt += 1
		tmp += c[j]
		ans = max(ans, tmp + sum_c * ((k - cnt) // num))
		j = p[j] - 1
if ans == 0:
	ans = max(c)
print(ans)


(N, K) = map(int, input().split())
P = [0] + list(map(int, input().split()))
C = [0] + list(map(int, input().split()))
ans = -float('inf')
for i in range(1, N + 1):
	v = i
	score = 0
	size = 0
	while True:
		size += 1
		score += C[v]
		if i == P[v]:
			break
		v = P[v]
	if score > 0:
		tmp = score * (K // size - 1)
		num = K % size + size
	else:
		tmp = 0
		num = min(K, size)
	v = i
	for _ in range(num):
		tmp += C[v]
		v = P[v]
		ans = max(tmp, ans)
print(ans)


(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):
	(start, count) = (i, 1)
	val = c[start]
	while p[start] - 1 != i:
		start = p[start] - 1
		count += 1
		val += c[start]
	start = i
	if val > 0:
		a = (k // count - 1) * val
		ans = max(a, ans)
		num = count + k % count
	else:
		a = 0
		num = min(k, count)
	for _ in range(num):
		a += c[start]
		start = p[start] - 1
		ans = max(a, ans)
print(ans)


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

def main():
	ans = -float('inf')
	for si in range(n):
		x = si
		S = []
		tot = 0
		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)
	return ans
print(main())


(N, K) = map(int, input().split())
P = list(map(int, input().split()))
P = [p - 1 for p in P]
C = list(map(int, input().split()))
vis = [False] * N
ans = [-float('inf')] * N
for root in range(N):
	if vis[root]:
		continue
	vis[root] = True
	cycle = [root]
	costs = [C[root]]
	u = P[root]
	vis[u] = True
	while u != root:
		cycle.append(u)
		costs.append(C[u])
		u = P[u]
		vis[u] = True
	L = len(cycle)
	S = sum(costs)
	for (i, v) in enumerate(cycle):
		cnt = 0
		for step in range(1, min(L, K) + 1):
			cnt += costs[(i + step) % L]
			val1 = cnt
			val2 = cnt + (K - step) // L * S
			ans[v] = max(ans[v], val1, val2)
print(max(ans))


from collections import deque
(N, K) = map(int, input().split())
P = list(map(int, input().split()))
C = list(map(int, input().split()))
A = -(1000000000.0 + 5)
for i in range(N):
	x = i
	S = deque()
	s = 0
	while True:
		x = P[x] - 1
		S.append(C[x])
		s += C[x]
		if x == i:
			break
	l = len(S)
	a = 0
	for i in range(l):
		a += S[i]
		if i + 1 > K:
			break
		An = a
		if s > 0:
			An += s * ((K - i - 1) // l)
		A = max(A, An)
print(A)


import sys
input = sys.stdin.readline
(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = -10 ** 18
for pos in range(n):
	value = 0
	points = []
	s = set()
	for j in range(n):
		s.add(pos)
		pos = p[pos] - 1
		value += c[pos]
		points.append(value)
		if pos in s:
			break
	loop_value = max(0, points[-1])
	l = len(s)
	for j in range(l):
		if j < k % l:
			ans = max(ans, points[j] + loop_value * (k // l))
		else:
			ans = max(ans, points[j] + loop_value * (k // l - 1))
print(ans)


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
ans = []
for i in range(n):
	ct = 0
	score = 0
	s = []
	pos = i
	while ct < k:
		ct += 1
		pos = p[pos] - 1
		score += c[pos]
		s.append(score)
		if pos == i:
			break
	if s[-1] < 0:
		ans.append(max(s))
	elif pos != i:
		ans.append(max(s))
	elif k % len(s) == 0:
		ans.append(s[-1] * (k // len(s) - 1) + max(s))
	else:
		ans.append(max(s[-1] * (k // len(s) - 1) + max(s), s[-1] * (k // len(s)) + max(s[0:k % len(s)])))
print(max(ans))


(n, k) = map(int, input().split())
p = list(map(int, input().split()))
c = list(map(int, input().split()))
p = [pi - 1 for pi in p]
ans = -1e+18
for i in range(n):
	cur = p[i]
	loop = [c[cur]]
	cnt = 1
	ans = max(ans, c[cur])
	while cur != i and cnt < k:
		cur = p[cur]
		tmp = loop[-1] + c[cur]
		loop.append(tmp)
		ans = max(ans, tmp)
		cnt += 1
	if cnt == k or loop[-1] <= 0:
		continue
	a = k // len(loop) * loop[-1]
	b = (k // len(loop) - 1) * loop[-1]
	ans = max(ans, a, b)
	for _ in range(k % len(loop)):
		a += c[cur]
		ans = max(ans, a)
		cur = p[cur]
	cur = i
	for _ in range(len(loop)):
		b += c[cur]
		ans = max(ans, b)
		cur = p[cur]
print(ans)


def resolve():
	INF = 10 ** 18
	(N, K) = map(int, input().split())
	P = list(map(lambda x: int(x) - 1, input().split()))
	C = list(map(int, input().split()))
	ans = -INF
	for s in range(N):
		S = []
		x = P[s]
		S.append(C[x])
		tot = C[x]
		while s != x:
			x = P[x]
			S.append(C[x])
			tot += C[x]
		s_n = len(S)
		t = 0
		for i in range(s_n):
			t += S[i]
			now = t
			if tot > 0:
				loop = (K - i - 1) // s_n
				now += tot * loop
			ans = max(ans, now)
	print(ans)
resolve()


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


def main():
	((n, k), p, c) = [[*map(int, t.split())] for t in open(0)]
	m = -10 ** 18
	for i in range(n):
		s = i
		t = 1
		x = c[s]
		while p[s] - 1 != i:
			s = p[s] - 1
			t += 1
			x += c[s]
		if x > 0:
			a = (k // t - 1) * x
			if a > m:
				m = a
			s = i
			for _ in range(k % t + t):
				s = p[s] - 1
				a += c[s]
				if a > m:
					m = a
		else:
			a = 0
			s = i
			for _ in range(min(k, t)):
				s = p[s] - 1
				a += c[s]
				if a > m:
					m = a
	print(m)
main()