一家航空公司推出了一项奇怪的奖励计划，为旅客提供免费航班。

该计划由两个整数 $m$ 和 $k$ 定义。在任意 $m$ 个连续的月份内，旅客必须为其中的至少 $k$ 次航班付费（如果该区间内的航班总数少于 $k$ 次，则所有航班都必须付费）。该区间内的其他航班则免费。请注意，此条件必须对所有 $m$ 个月的区间成立，包括所有在你的第一次飞行之前开始的区间。

你有一份未来多个月份的航班计划。你想知道你需要付费的最少航班次数。

输入格式

输入的第一行包含三个整数 $n, m$ ($1 \le n, m \le 2 \times 10^5$) 和 $k$ ($1 \le k \le 10^9$)，其中 $n$ 是你计划飞行未来连续的月份数，$m$ 和 $k$ 是航空公司奖励计划的参数。

接下来的 $n$ 行，每行包含一个整数 $f$ ($1 \le f \le 10^9$)，表示你计划在当月乘坐的航班数量。

输出格式

输出一个整数，表示你必须付费的最少航班次数。

样例

样例输入 1

8 3 2
3
1
4
1
5
9
2
6

样例输出 1

8