중력 발전소

중력 발전소란 중력의 힘을 이용하여 에너지를 생산하는 발전소이다. 중력 발전소는 수직으로 배열된 $N+1$개의 공간으로 구성된다. 각 공간에는 $0$번부터 $N$번까지 차례대로 번호가 매겨져 있다. 이때 가장 위에 위치한 공간이 $0$번, 가장 아래에 위치한 공간이 $N$번이다.

중력 발전소를 가동시키면, $0$번 공간에 공을 놓은 후 중력의 힘으로 공을 $N$번 공간까지 떨어뜨린다. 인접한 두 공간 사이에는 떨어지는 공을 감지할 수 있는 고리형 발전기가 있다. 구체적으로, $1 \leq i \leq N$에 대해 공이 $i - 1$번 공간에서 $i$번 공간으로 떨어질 경우 두 공간 사이의 고리형 발전기가 이를 감지하여 $A\_i$만큼의 에너지를 생산한다.

과학자들은 중력 발전소의 생산성을 높이기 위해 반중력 장치를 개발하였다. 중력 발전소에는 총 $\displaystyle \frac{N(N + 1)}{2}$개의 반중력 장치가 존재하며, 각 장치는 $0 \leq i < j \leq N$을 만족하는 정수 쌍 $(i, j)$에 대응된다. $(i, j)$에 대응되는 반중력 장치를 공이 $j$번 공간에 있을 때 사용하면 중력을 거슬러 공을 $i$번 공간으로 이동시킬 수 있다. 고리형 발전기는 공을 감지할 때마다 독립적으로 에너지를 생산하기 때문에 반중력 장치를 사용하여 각 고리형 발전기가 여러 번 에너지를 생산하도록 설계할 수 있다.

다만 반중력 장치는 중력 발전소를 불안정하게 만들 수 있기 때문에 사용에 몇 가지 제약이 존재한다.

• 반중력 장치를 사용할 때, 공이 거슬러 올라가는 공간의 개수마다 $K$만큼의 에너지를 소비한다. 즉, $(i, j)$에 대응되는 장치를 사용하면 $K \times (j-i)$ 만큼의 에너지를 소비한다.
• 각 반중력 장치는 최대 한 번만 사용될 수 있다.
• 반중력 장치를 사용하는 총 횟수는 최대 $M$번으로 제한되어 있다. 이때 $M$번을 모두 사용할 필요는 없다.

발전은 반드시 공을 $0$번 공간에 둔 상태에서 시작하고, 공이 $N$번 공간에 존재하는 상태에서 종료되어야 한다. 이때 공이 $N$번 공간에 있는 상태에서도 반중력 장치를 사용할 수 있다.

반중력 장치를 적절히 사용해 생산할 수 있는 총 에너지의 최댓값을 구하여라.

첫째 줄에 세 정수 $N$, $M$, $K$가 공백으로 구분되어 주어진다. ($1 \leq N \leq 100\\,000$; $0 \displaystyle \leq M \leq \min \left( \frac{N(N + 1)}{2}, {10}^9 \right)$; $0 \leq K \leq {10}^9$)

둘째 줄에 $N$개의 정수 $A\_1, A\_2, \cdots, A\_N$이 공백으로 구분되어 주어진다. ($1 \leq A\_i \leq {10}^9$; $\sum A\_i \leq {10}^9$)

생산할 수 있는 총 에너지의 최댓값을 출력한다.

첫 번째 예제의 경우 다음과 같은 방식으로 발전을 진행한다.

1. $0$번 공간의 공을 $7$번 공간까지 떨어뜨린다. 이때 총 $9 + 7 + 4 + 3 + 3 + 8 + 8 = 42$만큼의 에너지를 생산한다.
2. 반중력 장치를 사용하여 $7$번 공간의 공을 $0$번 공간으로 끌어올린다. 이때 $5 \times 7 = 35$만큼의 에너지를 소모한다.
3. 다시 $0$번 공간의 공을 $7$번 공간까지 떨어뜨린다. 1번 과정과 동일하게 $42$만큼의 에너지를 생산한다.

이때 총 $42 - 35 + 42 = 49$만큼의 에너지를 생산하며, 이보다 더 많이 생산할 수 없다.

두 번째 예제의 경우 반중력 장치를 사용하지 않는 것이 이득이며, 단순히 공을 떨어뜨리면 $1 + 2 + 3 + 4 = 10$만큼의 에너지를 생산할 수 있다.