题目描述

就在所有人都没有预料到的时候……萨什卡回来了。

在索菲亚轰轰烈烈的垃圾清理事件中，萨什卡最喜欢的一条街道上堆满了秋天落下的树叶。由于她非常热爱整洁，她决定亲自把街道的人行道清理干净。

更准确地说，人行道长度为 $N$ 米，被分成了 $N$ 个长度均为 $1$ 米的区间，从左到右依次编号为 $1,2,\dots,N$。第 $i$ 个区间中堆有 $V_i$ 立方米的树叶。每立方米树叶重 $1$ 千克。

在人行道最左端再往左 $1$ 米处，有一个装垃圾袋的地方，共有 $K$ 个垃圾袋。每个垃圾袋都足以装下整条人行道上的全部树叶。每个垃圾袋本身重量为 $C$。为方便起见，记垃圾袋来源点的位置为 $0$。

初始时，萨什卡站在位置 $0$。为了完成清理，她可以执行若干操作。设她当前站在位置 $X$，并且正携带总重量为 $W$ 的东西（即垃圾袋本身重量与袋中树叶重量之和），那么她可以：

• 从当前所在区间收集 $1$ 千克树叶放入袋中，即令 $V_X \to V_X-1$。要求 $X>0$ 且 $V_X>0$。该操作消耗 0 单位体力。
• 向左移动一个区间，即 $X \to X-1$。要求 $X>0$。该操作消耗 $W$ 单位体力。
• 向右移动一个区间，即 $X \to X+1$。要求 $X<N$，并且 当前位置的树叶必须已经清空，也就是 $V_X=0$，否则她无法穿过树叶。该操作消耗 $W$ 单位体力。
• 在垃圾袋来源点放下当前的装叶袋。要求 $X=0$，且当前手上拿着一个装过树叶的袋子。该操作消耗 0 单位体力。
• 在垃圾袋来源点拿起一个垃圾袋。要求 $X=0$，且当前没有拿着装叶袋。该操作消耗 0 单位体力。

清理完成时，目标是：

• 人行道上的所有树叶都已经被装进垃圾袋；
• 所有垃圾袋都位于起点位置 $0$。

请你编写程序 cleanup，求完成清理所需的最小体力值。

实现细节

你需要实现如下函数：

long long solve(const std::vector<long long> &V, int K, long long C)

• V：长度为 $N$ 的数组，表示树叶数量。其中 $V_1 = V[0], V_2 = V[1], \dots, V_N = V[N-1]$。
• K：垃圾袋数量。
• C：每个垃圾袋的重量。

该函数对每个测试点只会被调用一次，你需要返回一个整数，表示最小体力值。

输入格式（本地评测器）

• 第一行三个整数 $N,K,C$，表示人行道长度、垃圾袋数量以及每个垃圾袋的重量。
• 第二行 $N$ 个正整数 $V_1,V_2,\dots,V_N$，表示每个区间上的树叶数量。

输出格式（本地评测器）

• 输出一行一个整数，表示函数返回值。

样例 #1

输入

7 4 1
4 3 6 8 2 10 1

输出

199

样例 #2

输入

8 2 1
2 1 1 3 1 2 1 4

输出

133

样例 #3

输入

8 2 100
2 1 1 3 1 2 1 4

输出

1765

数据范围

• $1 \le K \le N \le 10^6$；
• $0 \le C \le 10^{12}$；
• $1 \le V_i \le 10^{12}$；
• $\sum_{i=1}^{N} V_i \le 10^{12}$。

子任务

只有当某个子任务以及其所依赖的所有子任务全部通过时，才能获得该子任务的分数。