Frequent Flier

Time limit2sMemory limit2048 MB

Summary

Given monthly flight counts, find the fewest flights you must pay for when every m consecutive months requires at least k paid flights or all flights in that span.

Level: Medium6 of 10
Topics: Dynamic programming, Sliding window, Prefix sum
Solved: No attempts yet

Problem

An airline runs a strange new rewards program that gives travelers free flights.

The program is set by two integers $m$ and $k$ . In any $m$ consecutive months, you must pay for at least $k$ of your flights. If there are fewer than $k$ flights in that span, you pay for all of them. The other flights in that span are free. This rule also applies to every $m$ -month span that starts before your first flight.

You have a schedule of how many flights you take in each of the next $n$ months. Find the minimum number of flights you must pay for.

Input

The first line contains three integers $n$ , $m$ ( $1 \le n,m \le 2 \times 10^5$ ) and $k$ ( $1 \le k \le 10^9$ ). Here $n$ is the number of consecutive months with planned flights, and $m$ and $k$ are the program parameters. Each of the next $n$ lines contains an integer $f$ ( $1 \le f \le 10^9$ ), the number of flights planned for that month.

Output

Output a single integer, the minimum number of planned flights you must pay for.

Examples1

Example 1
Input
```
8 3 2
3
1
4
1
5
9
2
6
```
Expected output
```
8
```