Guitarist

Interview

Time limit2sMemory limit128 MB

Summary

Given a starting volume and a sequence of forced up/down changes bounded by [0, M], find the maximum achievable volume for the last song using reachability DP.

Level: Medium4 of 10
Topics: Dynamic programming, Array
Solved: No attempts yet

Problem

Guitarist Kangto will play N songs in a fixed order during a concert. For this concert, the volume may be changed only right before each song starts.

Before the concert, an array V of length N was prepared. V[i] means that, before the i-th song starts, the current volume must be changed by exactly V[i], either up or down. If the current volume is P, then the i-th song can only be played at volume P + V[i] or P - V[i].

The volume must always be between 0 and M, inclusive. It cannot be changed to a value outside this range.

Given the number of songs N, the starting volume S, the maximum volume M, and the array V, find the maximum volume at which the last song can be played. The songs must be played in the given order.

Input

The first line contains N, S, and M. (1 <= N <= 50, 1 <= M <= 1,000, 0 <= S <= M)

The second line contains the volume differences V[1], V[2], ..., V[N] that must be applied before each song starts. Each value is between 1 and M, inclusive.

Output

Print the maximum possible volume for the last song. If it is impossible to reach the last song, print -1.

Hint

No additional hints are provided.

Examples3

Example 1
Input
```
3 5 10
5 3 7
```
Expected output
```
10
```
Example 2
Input
```
4 8 20
15 2 9 10
```
Expected output
```
-1
```

Example 3

Input

14 40 243
74 39 127 95 63 140 99 96 154 18 137 162 14 88

Expected output