选取秘藏

光砖铺完了，但Zero的迷宫里有秘藏——需要选取。

"秘藏？"CC问。

"对。"你说，"$n$个房间，每个房间有秘藏。从某个房间出发，走$k$步，每步可以去相邻房间。求经过的秘藏之和的最大值。"

"相邻？"

"对。"你说，"房间之间有通道。"

"$k$步？"

"对。"你说，"走$k$步，可以重复经过房间。"

"咋算？"

"倍增DP。"你说，"预处理走$2^j$步的最大值，然后拆$k$为二进制，组合起来。"

"倍增？"

"对。"你说，"先算走1步、2步、4步、8步……的最大值，然后用这些拼出走$k$步。"

"第47步。"你说，"$47=32+8+4+2+1$——5个倍增段组合。"

"组合？"

"对。"你说，"走32步后的最大值，再走8步……一步步拼。"

"秘藏会重复拿？"

"看规则。"你说，"如果重复经过算重复拿，要处理环；如果只能拿一次，是路径覆盖。"

"像寻宝？"

"对。"你说，"像寻宝——走迷宫，捡宝贝。"

"走哪条路？"

"算。"你说，"DP算出每步走哪最优。"

"能算出来？"

"能。"你说，"倍增让大$k$也能算。"

CC看着迷宫——像一个盒子，像一张网，像某种需要探索的空间。

"探索？"她问。

"对。"你说，"每一步都是选择——左还是右，前还是后。"

"选错？"

"可能错过秘藏。"你说，"但DP帮我们选最优的。"

"最优？"

"对。"你说，"不是唯一，但是最好。"

Echo把迷宫路径投射出来——弯弯曲曲，但每一段都是亮的。

"以前我迷路。"她说，"现在……有地图了。"

"因为你在画。"你说。

"对。"她说，"因为我在画。

题目描述

$n$个节点的图，每个节点有权值。从节点1出发，走$k$步，每步去相邻节点。求经过节点权值之和的最大值。

输入格式

第一行$n,m,k$。接下来$n$个整数权值。接下来$m$条边。

输出格式

最大权值和。

输入样例

1 0

输出样例

0

提示

• 倍增DP：$dp[j][u]$表示走$2^j$步到$u$的最大值。
• 转移：$dp[j][u]=\max(dp[j-1][v]+dp[j-1][u])$。
• 时间复杂度$O(n^3\log k)$。