题目背景

Games_OJ 和 YZOJ 联动啦！！！

题目描述

史蒂夫的村庄遭到了僵尸袭击！村庄有 $n$ 个防御点，每个防御点 $i$ 有防御值 $d_i$。僵尸会从第 $1$ 个防御点开始进攻，直至攻破村庄。

史蒂夫现在有两种方式增强防御：

1. 单独加固：消耗 $1$ 颗钻石，选择一个防御点 $i$ 使其防御值 $+1$（使 $d_i+1$）。
2. 连锁加固：消耗 $k$ 颗钻石，选择一个区间 $[l,r]$ 使区间内所有防御点防御值 $+1$（使 $d_{i\in[l,r]}+1$）。

僵尸们的总攻击力为 $A$，也就是说只有防御点的防御值都不小于 $A$，僵尸才无法入侵。史蒂夫希望用最少的钻石让村庄安全。

请你帮史蒂夫计算最少需要消耗多少颗钻石。

输入格式

第一行三个整数 $n,A,k$。

第二行 $n$ 个以空格隔开的整数 $d_i$，描述初始防御值。

输出格式

一个整数，表示最少需要消耗的钻石颗数。

输入输出样例

5 3 3
1 2 1 2 1

6

说明 / 提示

【样例解释】

1. 连锁加固 $[1,5]$，防御值变为 $2,3,2,3,2$，共消耗 $3$ 颗钻石。
2. 单独加固 $1,3,5$，防御值变为 $3,3,3,3,3$，共消耗 $3+3=6$ 颗钻石，同时 $d_i\ge A$。

【数据范围与约定】

对于 $100\%$ 的数据，$1 \le n \le 10^6,1 \le A \le 10^9,1 \le k \le 100,1 \le d_i \le 10^9$。