该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一个由 $N$ 个格子组成的棋盘上，编号分别为 $1, 2, \cdots, N$， Dash 准备使用一个棋子进行游戏。每个格子 $i$ 上写有一个整数 $C_i$。此外，给定一个 $1, 2, \cdots, N$ 的排列 $P_1, P_2, \cdots, P_N$。

Dash 可以选择任意一个格子放置棋子，然后进行 $1$ 到 $K$ 次移动。每次移动的规则如下：

• 如果棋子当前位于格子 $i$（$1 \leq i \leq N$），则将棋子移动到格子 $P_i$，并将 $C_{P_i}$ 加到当前得分上。

Dash 希望知道，游戏结束时可能得到的最大得分是多少？（游戏开始时的得分为 $0$。）

输入格式

第一行包含两个整数 $N、K$。

第二行输入 $N$ 个整数，表示 $P_1, P_2, \cdots, P_N$。

第三行输入 $N$ 个整数，表示 $C_1$ $C_2$ $\cdots$ $C_N$。

输出格式

输出一行一个整数表示答案。

样例

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

8

解释 #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$。

数据范围

• $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$