CF89A.Robbery

It is nighttime and Joe the Elusive got into the country's main bank's safe. The safe has n cells positioned in a row, each of them contains some amount of diamonds. Let's make the problem more comfortable to work with and mark the cells with positive numbers from 1 to n from the left to the right.

Unfortunately, Joe didn't switch the last security system off. On the plus side, he knows the way it works.

Every minute the security system calculates the total amount of diamonds for each two adjacent cells (for the cells between whose numbers difference equals 1). As a result of this check we get an n - 1 sums. If at least one of the sums differs from the corresponding sum received during the previous check, then the security system is triggered.

Joe can move the diamonds from one cell to another between the security system's checks. He manages to move them no more than m times between two checks. One of the three following operations is regarded as moving a diamond: moving a diamond from any cell to any other one, moving a diamond from any cell to Joe's pocket, moving a diamond from Joe's pocket to any cell. Initially Joe's pocket is empty, and it can carry an unlimited amount of diamonds. It is considered that before all Joe's actions the system performs at least one check.

In the morning the bank employees will come, which is why Joe has to leave the bank before that moment. Joe has only k minutes left before morning, and on each of these k minutes he can perform no more than m operations. All that remains in Joe's pocket, is considered his loot.

Calculate the largest amount of diamonds Joe can carry with him. Don't forget that the security system shouldn't be triggered (even after Joe leaves the bank) and Joe should leave before morning.

现在是深夜，神出鬼没的乔潜入了该国中央银行的保险库。保险库中有 $n$ 个单元格，从左到右排成一排，每个单元格中存放着一定数量的钻石。为便于处理问题，我们用从 $1$ 到 $n$ 的正整数对这些单元格进行编号（从左至右）。

不幸的是，乔未能关闭最后一道安保系统。但好消息是，他了解该系统的运行机制。

安保系统每分钟执行一次检查：计算每两个相邻单元格（即编号之差为 $1$ 的单元格对）中钻石总数。每次检查将得到 $n-1$ 个和值。若其中至少有一个和值与上一次检查所得对应和值不同，则安保系统将被触发。

乔可以在两次检查之间移动钻石，且在两次检查之间最多执行 $m$ 次操作。以下三种操作中的任意一种均视为“移动一颗钻石”：

• 将一颗钻石从任一单元格移至另一单元格；
• 将一颗钻石从任一单元格移入乔的口袋；
• 将一颗钻石从乔的口袋移至任一单元格。

初始时乔的口袋为空，且其容量无限。注意：在乔开始任何操作之前，安保系统已至少执行过一次检查。

清晨银行员工将抵达，因此乔必须在那之前离开银行。乔仅剩 $k$ 分钟时间（直至清晨），且在这 $k$ 分钟内的每一分钟，他最多可执行 $m$ 次操作。最终留在乔口袋中的钻石总量，即为其所获赃物。

请计算乔能带走的钻石最大数量。注意：安保系统绝不可被触发（即使在乔离开银行之后也必须满足此条件），且乔必须在清晨前离开。

The first line contains integers n, m and k (1 ≤ n ≤ 104, 1 ≤ m, k ≤ 109). The next line contains n numbers. The i-th number is equal to the amount of diamonds in the i-th cell — it is an integer from 0 to 105.

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n \leq 10^4$，$1 \leq m,\,k \leq 10^9$）。
下一行包含 $n$ 个数字。其中第 $i$ 个数字表示第 $i$ 个格子中的钻石数量——它是一个介于 $0$ 到 $10^5$ 之间的整数。

Print a single number — the maximum number of diamonds Joe can steal.

输出一个整数——Joe 能窃取的钻石的最大数量。

In the second sample Joe can act like this:

The diamonds' initial positions are 4 1 3.

During the first period of time Joe moves a diamond from the 1-th cell to the 2-th one and a diamond from the 3-th cell to his pocket.

By the end of the first period the diamonds' positions are 3 2 2. The check finds no difference and the security system doesn't go off.

During the second period Joe moves a diamond from the 3-rd cell to the 2-nd one and puts a diamond from the 1-st cell to his pocket.

By the end of the second period the diamonds' positions are 2 3 1. The check finds no difference again and the security system doesn't go off.

Now Joe leaves with 2 diamonds in his pocket.

在第二个样例中，Joe 可以按如下方式行动：

钻石的初始位置为：4 1 3。

在第一段时间内，Joe 将第 1 个格子中的一颗钻石移动到第 2 个格子，并将第 3 个格子中的一颗钻石放入自己的口袋。

第一段时间结束时，钻石的位置变为：3 2 2。检查未发现异常，因此安防系统未触发。

在第二段时间内，Joe 将第 3 个格子中的一颗钻石移动到第 2 个格子，并将第 1 个格子中的一颗钻石放入自己的口袋。

第二段时间结束时，钻石的位置变为：2 3 1。检查再次未发现异常，因此安防系统仍未触发。

此时，Joe 携带 2 颗钻石离开。