该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有 $n$ 个连续的房间，每个房间里放了 $a_i$ 个钻石。一共有 $k$ 分钟，每分钟能做 $m$ 次操作。可以的操作有：

• 把一颗钻石从某一堆移到另一堆。
• 把一颗钻石从某一堆中装进口袋。
• 把一颗钻石从口袋取出放入某一堆钻石。

要求：每分钟后，相邻两堆的钻石总数量不变。问 $k$ 分钟后最多可以带走多少钻石。

输入格式

第一行三个整数 $n,m,k$，$2 \le n \le 10^4$，$1 \le m, k \le 10^9$。

第二行 $n$ 个整数 $a_i$，$0 \le a_i \le 10^5$。

输出格式

一个整数表示答案。

2 3 1
2 3

0

3 2 2
4 1 3

2