### Zonal Computing Olympiad 2010, 12 Dec 2009

### 10:00 am–1:00 pm IST

### Problem 1 : Sequence game

You are given a sequence of *N* positive
integers *i*_{1},
*i*_{2}, …, *i*_{N}. In
addition, you are given a starting integer *b* and lower
and upper integer limits *min* and *max*,
respectively. Note that 0 ≤ *min* ≤ *b* ≤ *max* always.

The sequence game is played as follows. Initially, your score
is *b*. In step 1, you can either add
*i*_{1} to *b* or
subtract *i*_{1} from *b* to get a new
score *b*_{1}. In step 2, you
update *b*_{1} by adding or
subtracting *i*_{2} to get a new
score *b*_{2}. Proceeding in this way, in
step *j*, you update *b*_{j-1} by adding
or subtracting *i*_{j} to get a new
score *b*_{j}. The rule is that each
score *b*_{j} should always lie
between *min* and *max*, inclusive: that is,
for each *j*, 1 ≤ *j*
≤ *N*, it should be the case that *min ≤
b*_{j} ≤ max. Your final score
is *b*_{N}, after using the last number in the
sequence.

Your aim is to maximise your final score while playing
according to the rules. If there is no way to complete
all *N* steps without going outside the
bounds *min* and *max*, your score is -1.

For example, suppose the sequence of numbers you have is
[2,3,4], *b* is 5, *min* is 0 and *max* is
8. After step 1, the score can be 3 or 7. After step 2, the
score can be 0, 4, or 6. A score of 10 is not allowed
since *max* is 8. After step 3, the score can be 0, 2,
4, or 8. Thus, in this game, the maximum score you can obtain
at the end of the sequence is 8.

### Input format

The first line of the input contains four integers *N*,
*b*, *min* and *max*, whose meaning is as
explained above. The second line of input contains *N*
space separated integers, the sequence over which the game is
played.

### Output format

Your output should be a single line consisting of one integer,
the maximum final score that you can achieve.

### Testdata

In all cases, N ≤ 10^{3} and
0 ≤ *min* ≤ *b* ≤ *max* ≤ 10^{3}.

### Sample Input

3 5 0 8
2 3 4

### Sample Output

8