配点 : $400$ 点

問題文

高橋君は $1, 2, \cdots, N$ の番号のついた $N$ マスから成るマス目の上で、コマを使ってゲームを行おうとしています。マス $i$ には整数 $C_i$ が書かれています。また、$1, 2 \cdots , N$ の順列 $P_1, P_2, \cdots, P_N$ が与えられています。

これから高橋君は好きなマスを $1$ つ選んでコマを $1$ つ置き、$1$ 回以上 $K$ 回以下の好きな回数だけ、次のような方法でコマを移動させます。

• $1$ 回の移動では、現在コマがマス $i (1 \leq i \leq N)$ にあるなら、コマをマス $P_i$ に移動させる。このとき、スコアに $C_{P_i}$ が加算される。

高橋君のために、ゲーム終了時のスコアとしてあり得る値の最大値を求めてください。(ゲーム開始時のスコアは $0$ です。)

制約

• $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$ は全て異なる
• $-10^9 \leq C_i \leq 10^9$
• 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$

$P_1$ $P_2$ $\cdots$ $P_N$

$C_1$ $C_2$ $\cdots$ $C_N$

出力

ゲーム終了時のスコアとしてあり得る値の最大値を出力せよ。

5 2
2 4 5 1 3
3 4 -10 -8 8

8

好きなマスから始めて $2$ 回以下コマを移動させる方法は以下の通りです。

• 初めマス $1$ にコマを置く場合。$1$ 回移動するとマス $2$ に動き、スコアが $4$ になる。$2$ 回移動するとマス $4$ に動き、スコアが $4 + (-8) = -4$ になる。
• 初めマス $2$ にコマを置く場合。$1$ 回移動するとマス $4$ に動き、スコアが $-8$ になる。$2$ 回移動するとマス $1$ に動き、スコアが $-8 + 3 = -5$ になる。
• 初めマス $3$ にコマを置く場合。$1$ 回移動するとマス $5$ に動き、スコアが $8$ になる。$2$ 回移動するとマス $3$ に動き、スコアが $8 + (-10) = -2$ になる。
• 初めマス $4$ にコマを置く場合。$1$ 回移動するとマス $1$ に動き、スコアが $3$ になる。$2$ 回移動するとマス $2$ に動き、スコアが $3 + 4 = 7$ になる。
• 初めマス $5$ にコマを置く場合。$1$ 回移動するとマス $3$ に動き、スコアが $-10$ になる。$2$ 回移動するとマス $5$ に動き、スコアが $-10 + 8 = -2$ になる。

これらの最大値は $8$ です。

2 3
2 1
10 -7

13

3 3
3 1 2
-1000 -2000 -3000

-1000

最低 $1$ 回はコマを移動させる必要があります。

10 58
9 1 6 7 8 4 3 2 10 5
695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719

29507023469

答えの絶対値は非常に大きくなる場合があります。