Codeforces and Polygon may be unavailable from May 23, 4:00 (UTC) to May 23, 8:00 (UTC) due to technical maintenance. ×
B. Sanity
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Bossologist is slowly losing his sanity! Bossologist starts off with $$$S$$$ sanity points, for every email Chessbot sends from polygon, he loses $$$1$$$ sanity point. The problem writing process lasts $$$N$$$ days, where each day Chessbot sends between $$$0$$$ and $$$1000$$$ emails (inclusive). Given that Bossologist will gain $$$1$$$ sanity point for every $$$K$$$ days in a row that he doesn't get an email, calculate the number of sanity points he has at the end of $$$N$$$ days.

Note: It is guaranteed that Bossolgist's sanity will always be non-negative for the entire problem writing process.

Input

The first line contains $$$N$$$ ($$$1 \leq N \leq 10^5$$$), $$$S$$$ ($$$1 \leq S \leq 10^9$$$), and $$$K$$$ ($$$1 \leq K \leq 1000$$$).

The next line contains $$$N$$$ integers where the $$$i$$$'th number denotes the number of emails Chessbot sends on day $$$i$$$.

Output

Output Bossologist's sanity at the end of the $$$N$$$ days.

Example
Input
7 10 3
3 0 0 0 0 0 0
Output
9
Note

On the first day Bossologist loses $$$3$$$ sanity points since Chessbot sent $$$3$$$ emails. However he then gains $$$2$$$ sanity points back since by day $$$7$$$ Bossologist has not recieved an email for $$$6$$$ days. So he therefore ends the $$$7$$$ days with a sanity of $$$9$$$.

$$$-------------------------------------------------$$$

Idea: Bossologist

Preparation: Bossologist

Occurences: Novice 2