/ 
実行時間制限: 3 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
高橋君は 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 です。)
制約
- 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
出力
ゲーム終了時のスコアとしてあり得る値の最大値を出力せよ。
入力例 1
5 2 2 4 5 1 3 3 4 -10 -8 8
出力例 1
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
2 3 2 1 10 -7
出力例 2
13
入力例 3
3 3 3 1 2 -1000 -2000 -3000
出力例 3
-1000
最低 1 回はコマを移動させる必要があります。
入力例 4
10 58 9 1 6 7 8 4 3 2 10 5 695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719
出力例 4
29507023469
答えの絶対値は非常に大きくなる場合があります。
Score : 400 points
Problem Statement
Takahashi will play a game using a piece on an array of squares numbered 1, 2, \cdots, N. Square i has an integer C_i written on it. Also, he is given a permutation of 1, 2, \cdots, N: P_1, P_2, \cdots, P_N.
Now, he will choose one square and place the piece on that square. Then, he will make the following move some number of times between 1 and K (inclusive):
- In one move, if the piece is now on Square i (1 \leq i \leq N), move it to Square P_i. Here, his score increases by C_{P_i}.
Help him by finding the maximum possible score at the end of the game. (The score is 0 at the beginning of the game.)
Constraints
- 2 \leq N \leq 5000
- 1 \leq K \leq 10^9
- 1 \leq P_i \leq N
- P_i \neq i
- P_1, P_2, \cdots, P_N are all different.
- -10^9 \leq C_i \leq 10^9
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N K P_1 P_2 \cdots P_N C_1 C_2 \cdots C_N
Output
Print the maximum possible score at the end of the game.
Sample Input 1
5 2 2 4 5 1 3 3 4 -10 -8 8
Sample Output 1
8
When we start at some square of our choice and make at most two moves, we have the following options:
- If we start at Square 1, making one move sends the piece to Square 2, after which the score is 4. Making another move sends the piece to Square 4, after which the score is 4 + (-8) = -4.
- If we start at Square 2, making one move sends the piece to Square 4, after which the score is -8. Making another move sends the piece to Square 1, after which the score is -8 + 3 = -5.
- If we start at Square 3, making one move sends the piece to Square 5, after which the score is 8. Making another move sends the piece to Square 3, after which the score is 8 + (-10) = -2.
- If we start at Square 4, making one move sends the piece to Square 1, after which the score is 3. Making another move sends the piece to Square 2, after which the score is 3 + 4 = 7.
- If we start at Square 5, making one move sends the piece to Square 3, after which the score is -10. Making another move sends the piece to Square 5, after which the score is -10 + 8 = -2.
The maximum score achieved is 8.
Sample Input 2
2 3 2 1 10 -7
Sample Output 2
13
Sample Input 3
3 3 3 1 2 -1000 -2000 -3000
Sample Output 3
-1000
We have to make at least one move.
Sample Input 4
10 58 9 1 6 7 8 4 3 2 10 5 695279662 988782657 -119067776 382975538 -151885171 -177220596 -169777795 37619092 389386780 980092719
Sample Output 4
29507023469
The absolute value of the answer may be enormous.