← 返回题目列表

AtCoder · abc175_d

D. 移动件

中文机器翻译题面 查看原题

分数: 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

答案的绝对价值可能是巨大的。