← 返回题目列表

Codeforces · 89/A

A. 抢劫

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

夜里,神出鬼没的乔进入了该国主要银行的保险箱。保险箱有 n 个连续排列的单元格,每个单元格都包含一定数量的钻石。让我们让问题更容易处理,并从左到右用 1 到 n 的正数标记单元格。

不幸的是,乔没有关闭最后一个安全系统。从好的方面来说,他知道它是如何运作的。

每分钟,安全系统都会计算每两个相邻单元格(对于数量差等于 1 的单元格)的钻石总量。作为这次检查的结果,我们得到了 n - 1 个和。如果至少有一个金额与前一次检查期间收到的相应金额不同,则触发安全系统。

乔可以在安全系统的检查之间将钻石从一个牢房移动到另一个牢房。他设法在两次检查之间移动它们不超过 m 次。以下三个操作之一被视为移动钻石:将钻石从任何单元移动到任何其他单元,将钻石从任何单元移动到乔的口袋,将钻石从乔的口袋移动到任何单元。最初乔的口袋是空的,并且可以携带无限数量的钻石。认为在 Joe 的所有操作之前,系统至少执行一项检查。

早上银行员工会来,这就是为什么乔必须在那一刻之前离开银行。距离早晨,Joe 只剩下 k 分钟的时间,而在这 k 分钟的每一分钟里,他最多只能执行 m 个操作。乔口袋里剩下的所有东西都被认为是他的战利品。

计算乔可以随身携带的最大钻石数量。不要忘记安全系统不应该被触发(即使在乔离开银行之后)并且乔应该在早上之前离开。

输入

第一行包含整数 n、m 和 k (1 ≤ n ≤ 104, 1 ≤ m, k ≤ 109)。下一行包含 n 个数字。第 i 个数字等于第 i 个单元格中钻石的数量 - 它是 0 到 105 之间的整数。

输出

打印一个数字——乔可以偷走的最大钻石数量。

示例

输入 #1

2 3 1
2 3

输出 #1

0

输入 #2

3 2 2
4 1 3

输出 #2

2

注意

在第二个示例中,Joe 可以执行如下操作:

菱形的初始位置是 4 1 3。

在第一个时间段内,乔将一颗钻石从第 1 个单元格移至第 2 个单元格,并将一颗钻石从第 3 个单元格移至他的口袋。

第一个周期结束时,钻石的位置为 3 2 2。检查没有发现任何差异,安全系统也不会关闭。

在第二个周期中,乔将一颗钻石从第三个单元格移到第二个单元格,并将一颗钻石从第一个单元格放入他的口袋。

第二期结束时,钻石的位置为 2 3 1。检查再次没有发现任何差异,安全系统也不会关闭。

现在 Joe 离开时口袋里揣着 2 颗钻石。