分数: 400 点
问题陈述
高桥将使用棋子玩一个游戏,棋子放在编号为 的方格数组上 1, 2, \cdots, 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 在游戏开始时。)
约束
- 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
当我们从我们选择的某个方格开始并最多进行两次移动时,我们有以下选择:
- 如果我们从 Square 开始 1,走一步将棋子发送到方格 2,之后得分为 4。再走一步会将棋子发送到 Square 4,之后得分为 4 + (-8) = -4.
- 如果我们从 Square 开始 2,走一步将棋子发送到方格 4,之后得分为 -8。再走一步会将棋子发送到 Square 1,之后得分为 -8 + 3 = -5.
- 如果我们从 Square 开始 3,走一步将棋子发送到方格 5,之后得分为 8。再走一步会将棋子发送到 Square 3,之后得分为 8 + (-10) = -2.
- 如果我们从 Square 开始 4,走一步将棋子发送到方格 1,之后得分为 3。再走一步会将棋子发送到 Square 2,之后得分为 3 + 4 = 7.
- 如果我们从 Square 开始 5,走一步将棋子发送到方格 3,之后得分为 -10。再走一步会将棋子发送到 Square 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
我们必须至少采取一项行动。
示例输入 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
答案的绝对价值可能是巨大的。