CF89A Robbery

夜幕降临，Joe the Elusive 潜入了国家银行的主金库。金库内有 $n$ 个保险箱格子，依次排成一行，每格都装有若干钻石。为了方便，我们将这些格子自左向右依次标号为 $1$ 到 $n$。 不幸的是，Joe 忘记关闭最后一道安保系统。但幸运的是，他知道系统的工作原理。 每一分钟，安保系统会计算所有相邻的两个格子的钻石总数（即编号之差为 $1$ 的每对格子的钻石数之和）。因此每次检查得到 $n-1$ 个和。如果当前检查得到的任意一个和与上一次检查时的对应和不同，安保系统就会被触发。 在每次安保系统检查之间，Joe 可以在格子间搬运钻石。在两次检查之间，他最多能进行 $m$ 次搬运操作。以下三种操作都算作一次搬运：从任意一个格子搬出一颗钻石放入另一个格子、从任意格子拿一颗钻石放入口袋、或从口袋中取出一颗钻石放入任意格子。起初，Joe 的口袋是空的，但口袋容量无限。系统第一次检查在所有行动前就已执行过。 到了早上，银行员工就会来，因此 Joe 必须天亮前离开银行。天亮还有 $k$ 分钟，每分钟 Joe 可以进行最多 $m$ 次操作。留在 Joe 口袋中的钻石将归他所有。 请计算 Joe 能带走的最大钻石数量。注意，在 Joe 离开银行之后，也不能触发安保系统。

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n \leq 10^4$，$1 \leq m, k \leq 10^9$）。第二行有 $n$ 个数，第 $i$ 个数表示第 $i$ 个格子里的钻石数量，为 $0$ 到 $10^5$ 的整数。

输出一个整数，表示 Joe 最多可以偷走的钻石数量。

在第二个样例中，Joe 可以这样操作： 钻石的初始分布为 $4$ $1$ $3$。 在第一轮，Joe 将第 $1$ 个格子的一个钻石移到第 $2$ 个格子，将第 $3$ 个格子的一个钻石放进口袋。 第一轮结束后，钻石分布变为 $3$ $2$ $2$。安保设备检查后未发现变化。 在第二轮，Joe 将第 $3$ 个格子的一个钻石移到第 $2$ 个格子，并从第 $1$ 个格子拿一个钻石入口袋。 第二轮结束后，钻石分布变为 $2$ $3$ $1$。系统检查后仍未发现变化。 此时 Joe 口袋中有 $2$ 颗钻石，可以顺利离开。 由 ChatGPT 5 翻译