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.

题目描述

一只机械乌鸦，只会机械性执行任务。它的面前有一个容量为 $m$ 的瓶子，初始时瓶子的水量为 $x$ 。有 $n$ 次任务需要乌鸦执行。每次任务有一个参数 $c_i$，表示可以往瓶子中加入 $c_i$ 的水，或者喝掉 $c_i$的水，乌鸦可以选择加入 $c_i$ 的水或者喝掉 $c_i$ 的水。加入或者喝掉 $c_i$ 的水，得符合实际情况，如果加入 $c_i$ 的水已经超过瓶子的容量了，则不能加入，如果瓶子里剩余的水不足 $c_i$了，也是不能喝掉的。

如果在执行某次任务时，即不能加入水也不能喝掉水，则任务失败。

请你计算，$n$ 个任务完成后，水容器中的最大水量。

输入格式

第一行依次输入 $n,x,m$。

第二行依次输入 $n$ 个值，代表每次任务给定的 $c_i$。

输出格式

输出 $n$ 个任务完成后瓶子中的最大水量。

如果有某个任务失败，则输出 $-1$。

样例输入输出

3 3 9
1 1 5 

8

3 1 15
7 12 14 

-1

说明/提示

样例1：总共有 $3$ 个任务，瓶子初始水量为 $3$， 最大容量为 $9$。第一次任务时可以喝掉容量为 $1$ 的水，第二次任务时加入容量为 $1$ 的水，第三次任务时加入容量为 $5$ 的水。最后瓶子有容量为 $8$ 的水。其他方案最后的值不会大于 $8$。

样例2：总共有 $3$ 个任务，瓶子初始水量为 $1$， 最大容量为 $15$。第一次任务时只能加入容量为 $7$ 的水，第二次任务既不能加入也不能喝掉容量为 $12$ 的水。

数据范围

对于 $100\%$ 的数据，$1 \le n \le 50,1 \le m \le 1000,0 \le x,c_i \le m$。