P16075 [ICPC 2023 NAC] Frequent Flier

An airline is offering a strange new rewards program to offer free flights to travelers. The program can be parameterized with two integers $m$ and $k$. Within any $m$ consecutive months, a traveler must pay for at least $k$ of those flights (if there are fewer than $k$ flights in that interval, all of those flights must be paid for). Other flights within that interval are free. Note that this condition needs to be true for all $m$-month intervals, including all of the ones that start before your first flight. You have a schedule of the number of flights you’ll take over the next many months. You want to know the minimum number of flights you’ll need to pay for.

The first line of input contains three integers $n$, $m$ ($1 \leq n, m \leq 2 \times 10^5$) and $k$ ($1 \leq k \leq 10^9$), where $n$ is the number of consecutive months ahead that you have flights planned, and $m$ and $k$ are the parameters of the airline’s rewards program. Each of the next $n$ lines contains an integer $f$ ($1 \leq f \leq 10^9$), which is the number of flights you plan to take during that month.

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