409957: GYM103870 B Sanity

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

B. Sanitytime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard 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.

ExampleInput
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

加入题单

上一题 下一题 算法标签: