AT_abc175_d [ABC175D] Moving Piece

[problemUrl]: https://atcoder.jp/contests/abc175/tasks/abc175_d 高橋君は $ 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 $

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

### 制約 - $ 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 答えの絶対値は非常に大きくなる場合があります。