重力发电厂是一种利用重力发电的发电厂。一个重力发电厂由垂直排列的 $N + 1$ 个区域组成。这些区域从 $0$ 到 $N$ 依次编号。最上方的区域编号为 $0$，最下方的区域编号为 $N$。
为了运行重力发电厂，需要将一个球从区域 $0$ 释放并下落到区域 $N$。在每两个相邻区域之间，有一个可以检测下落球体的环形发电机。具体来说，当球从区域 $i - 1$ 下落到区域 $i$ 时，环形发电机产生 $A_i$ 的能量，其中 $1 \le i \le N$。
为了提高重力发电厂的能量输出，科学家们开发了一种反重力装置。重力发电厂中总共有 $\frac{N(N+1)}{2}$ 个反重力装置，每个装置都被分配了一个整数对 $(i, j)$，其中 $0 \le i < j \le N$。分配给 $(i, j)$ 的反重力装置可以用来克服重力，将位于区域 $j$ 的球移动到区域 $i$。由于每次球穿过时环形发电机都会独立运行，因此可以使用反重力装置让发电机多次发电。
然而，反重力装置会使重力发电厂变得不稳定，因此它们的使用存在一些限制。
- 激活反重力装置时，球每向上移动一个区域就需要消耗 $K$ 的能量。因此，激活分配给 $(i, j)$ 的装置需要消耗 $K \times (j - i)$ 的能量。
- 每个反重力装置最多只能使用一次。
- 反重力装置总共最多可以使用 $M$ 次。不需要恰好使用 $M$ 次。
发电过程总是从球最初放置在区域 $0$ 开始，并且必须在球位于区域 $N$ 时结束。然而，即使球已经到达区域 $N$，也可以使用反重力装置。
求合理使用反重力装置所能获得的最大总能量。
输入格式
输入的第一行包含三个空格分隔的整数 $N, M, K$。（$1 \le N \le 100\,000$；$0 \le M \le \min(\frac{N(N+1)}{2}, 10^9)$；$0 \le K \le 10^9$）
输入的第二行包含 $N$ 个空格分隔的整数 $A_1, A_2, \dots, A_N$。（$1 \le A_i \le 10^9$；$\sum A_i \le 10^9$）
输出格式
在第一行输出可以获得的最大总能量。
样例
输入样例 1
7 1 5 9 7 4 3 3 8 8
输出样例 1
49
输入样例 2
4 3 100 1 2 3 4
输出样例 2
10
输入样例 3
5 5 4 7 3 7 3 7
输出样例 3
52
说明
对于第一个样例，可以通过以下方式发电：
- 将球从区域 $0$ 释放并下落到区域 $7$。这会产生 $9 + 7 + 4 + 3 + 3 + 8 + 8 = 42$ 的能量。
- 使用一个反重力装置将球从区域 $7$ 移动到区域 $0$。这会消耗 $5 \times 7 = 35$ 的能量。
- 再次将球从区域 $0$ 释放并下落到区域 $7$。这会产生 $42$ 的能量，与步骤 1 相同。
获得的总能量为 $42 - 35 + 42 = 49$，可以证明这是所能获得的最大总能量。
对于第二个样例，最好完全不使用反重力装置。只需简单地让球下落即可产生 $1 + 2 + 3 + 4 = 10$ 的能量。