移动棋子

题目描述

高桥君打算在由编号 $1, 2, \cdots, N$ 的 $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$。)

输入格式

输入按以下格式从标准输入给出:

$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

答案的绝对值有时会非常大。

数据范围

• $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$
• 输入均为整数