M. Ali and BOX
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

$$$Ali$$$ is playing a very boring game called BOX. In this game, you have a box that contains $$$x$$$ coins, and there is a road which contains $$$n$$$ checkpoints where you can get or lose coins. The road can be represented as an array $$$a$$$ containing $$$n$$$ integers where $$$a_i$$$ represents the amount of coins that you may gain or lose at the $$$ith$$$ checkpoint. You start at the beginning of the road "at index $$$0$$$". The game goes as follows:

You start at index zero with an initial amount of coins equals to $$$x$$$. You start visiting the checkpoints from left to right without skipping any of them and with the capability of ending the game any time you want.

At each checkpoint, you get or lose an amount of coins defined by $$$a_i$$$. If at any point, the total amount of coins you have becomes negative, you lose the game.

You can do this operation only for once: pay $$$c$$$ coins "if you have them" and choose an index $$$i$$$ where $$$i$$$ is after your current checkpoint, then reverse the subsegment $$$[i,n]$$$.

The goal of the game is to maximize the amount of coins you have. Ali isn't very good at this kind of game (he only plays shooters) so he asked you to help him. Can you find the maximum amount of coins Ali can get?

Input

The first line contains three integers: $$$n,x,c$$$ $$$(1 \le n \le 10^6) , (0 \le x,c \le 10^9)$$$, number of checkpoints, the initial value of coins in the box, and the cost of flipping a segment.

The second line contains $$$n$$$ integers, $$$a_1 , a_2, ... , a_n$$$ $$$(-10^9 \le a_i \le 10^9)$$$

Output

Print one integer, the maximum amount of coins Ali can get.

Examples
Input
4 0 1
1 -2 3 4
Output
7
Input
13 19 22
12 30 -1 15 -55 -9 17 5 -4 6 -15 10 15
Output
87
Note

In the first example, we move to the first checkpoint and add it to $$$x$$$, so now $$$x=1$$$, then we pay $$$c=1$$$ and flip the subsegment $$$[2,4]$$$, so the array becomes: $$$[$$$$$$1$$$ $$$4$$$ $$$3$$$ $$$-2$$$$$$]$$$, now we move to the second and the third checkpoints and then we end the game, so the final result will be: $$$x=0+1-1+4+3=7$$$.