You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

一场比赛需要一个送分题。

题目描述

给定初始值 $s$ 和一个极限值 $max$ 和一个长度为 $n$ 的序列 $A_1,A_2,A_3...A_n$ ，你需要依次执行操作。记当前值为 $now$ $($初始为$s)$ , 对于第 $i$ 次操作，你需要将当前值 $now$ 转变为 $now+A_i$ 或者 $now-A_i$ 。对于所有时刻，都需要保证 $now$ $\le$ $max$ 并且 $now$ $\ge 0$ 。我们希望经过 $n$ 次操作后当前值 $now$ 的值最大，你需要输出这个最大值。如果无论如何也无法使 $0 \le now \le max$ ，输出 $-1$ 。

输入格式

输入格式共两行。

第一行三个整数 $n,s,max$ 。

第二行为序列$A$，$A_1,A_2,A_3\dots A_n$。

输出格式

输出一行一个整数 $now$

3 5 10
5 3 7

10

数据范围

对于 $30\%$ 的数据：$n=1$ 。

对于 $60\%$ 的数据：$n\le50$ 。

对于 $100\%$ 的数据：$n\le1000,1 \le max \le 1000,0 \le s \le max$ 。