Edward is playing the sneaky golem deck. He just finished a game and you have the log of the actions (cards he played) in the game. You really want to know whether or not he played his sneaky golem, but because golem is so sneaky, the transcript does not show the golem. Thus, you will do the next best thing: use the game log to find out if it was ever possible that Edward played his sneaky golem. The sneaky golem costs $$$G$$$ elixir.
The game log is an array of $$$T$$$ non-negative integers, denoting how much elixir Edward spent at each timestep. This game log does not capture any possible elixir spent playing the golem.
Between each timestep, Edward gains $$$1$$$ elixir. Edward can have a maximum of $$$E$$$ elixir. He starts at the first timestep with $$$E$$$ elixir. He can never have more than $$$E$$$ elixir, nor can he have negative elixir.
Please find if it was possible that at any point in the game, Edward played his sneaky golem.
The first line contains $$$T$$$, $$$E$$$, and $$$G$$$. $$$1 \leq T \leq 10^5$$$, $$$1 \leq E \leq 10^9$$$, $$$1 \leq G \leq E$$$.
The second line contains $$$T$$$ integers, $$$t_1, t_2, ..., t_T$$$, where $$$t_i$$$ represents the elixir spent at timestep $$$i$$$, excluding any sneaky golem plays. $$$0 \leq t_i \leq E$$$.
It is guaranteed that this sequence is valid (Edward's elixir never goes negative).
Output $$$YES$$$ if it was possible that Edward played his sneaky golem, $$$NO$$$ otherwise.
4 10 8 2 0 0 3
YES
1 10 8 5
NO
In the first test case, Edward could have played his sneaky golem at the first timestep. Then, he would have 3 elixir by the 4th timestep, which is valid.
In the second test case, there is only one opportunity for Edward to play his sneaky golem, at the first timestep. However, doing so needs 13 elixir, which will cause Edward to go negative. Edward cannot have negative elixir so this cannot have happened. Thus, unfortunately, it is not possible for sneaky golem's time to have come.
