题目描述

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

该计划可以用两个整数 $m$ 和 $k$ 来参数化。在任意连续的 $m$ 个月内，旅客必须为其中至少 $k$ 个航班付费（如果该时间段内的航班数少于 $k$，则所有航班都必须付费）。该时间段内的其他航班可以免费。注意，这个条件需要适用于所有以月为单位的连续 $m$ 个月的时间区间，包括那些在你第一次航班之前就开始的区间。

你有一个未来许多个月的航班计划表，列出了每个月你将乘坐的航班数量。你想知道你需要付费的最少航班数量。

输入格式

输入的第一行包含三个整数 $n$、$m$（$1 \leq n, m \leq 2 \times 10^5$）和 $k$（$1 \leq k \leq 10^9$），其中 $n$ 是你有航班计划的连续月数，$m$ 和 $k$ 是航空公司奖励计划的参数。

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

输出格式

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

8 3 2
3
1
4
1
5
9
2
6

8

提示

翻译由 DeepSeek V3.2 完成