题目描述

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

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

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

输入格式

第一行三个整数 $n,m,k$，$1 \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