AT_abc175_d [ABC175D] Moving Piece

高桥君打算在由编号为 $1, 2, \cdots, N$ 的 $N$ 个格子组成的棋盘上，用棋子玩一个游戏。每个格子 $i$ 上写有一个整数 $C_i$。此外，还给定了一个 $1, 2, \cdots, N$ 的排列 $P_1, P_2, \cdots, P_N$。 接下来，高桥君可以任选一个格子放置一个棋子，并且可以选择移动棋子的次数，次数不少于 $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$

输出游戏结束时可能获得的最大分数。

## 限制条件 - $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$ - 输入均为整数 ## 样例解释 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$。 ## 样例解释 3 必须至少移动 $1$ 次棋子。 ## 样例解释 4 答案的绝对值可能会非常大。 由 ChatGPT 4.1 翻译