题目描述

高橋君は $1,\ 2,\ \cdots,\ N$ の番号のついた $N$ マスから成るマス目の上で、コマを使ってゲームを行おうとしています。マス $i$ には整数 $C_i$ が書かれています。また、$1,\ 2\ …,\ 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$ です。)

输入格式

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

$N$ $K$ $P_1$ $P_2$ $\cdots$ $P_N$ $C_1$ $C_2$ $\cdots$ $C_N$

输出格式

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

题目大意

高桥将用一枚棋子在编号为 $1, 2, \cdots, N$ 的数组方格上下棋。方格 $i$ 上写着一个整数 $C_i$。

此外，他还得到了一个 $1, 2, \cdots, N$ 的排列组合：$P_1, P_2, \cdots, P_N$。

现在，他将选择一个方格并将棋子放在该方格上。然后，他将在 $1$ 和 $K$ 之间（包括 $1$ 和 $K$）下若干次棋：

• 在一步棋中，如果棋子现在在 $i$ 位 $(1 \leq i \leq N)$，将其移动到 $P_i$ 位置。在这里，他的得分会增加 $C_{P_i}$。

帮助他找出对局结束时的最大可能得分。(游戏开始时的得分是 $0$）。

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

8

2 3
2 1
10 -7

13

3 3
3 1 2
-1000 -2000 -3000

-1000

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

29507023469

提示

制約

• $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$
• 入力は全て整数である

Sample Explanation 1

好きなマスから始めて $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$ です。

Sample Explanation 3

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

Sample Explanation 4

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