又掉分了
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
64bit IO Format: %lld

题目描述

小R nowforces 又掉分了。
小R伤心欲绝，在梦中小R梦到了接下来 \ n\ 次比赛的表现分，他立马惊醒将所有场次的表现分记录了下来。某一场比赛的加分规则为当前分数+\ ⌊\frac{(表现分-当前分数)}{2}⌋\
现在给出小R当前的分数，若梦中的情况会如实发生在现实中，请帮小R选出任意(可能为0)几场比赛参加，使得最后的分数最大，并计算最大分数。

注意表现分按时间顺序给出，小R也只能按照时间顺序参加比赛，即参加了第 \ i\ 场比赛后不能继续参加第 \ i\ 场之前的比赛。

\ ⌊x⌋\表示将\ x\向零取整，比如\ ⌊2.3⌋=2\ \ ⌊3.9⌋=3\ \ ⌊-3.4⌋=-3\。

输入描述:

第一行输入一个整数\ x\ \ (0\leq x\leq 3000)--小R的当前分数

第二行输入一个整数\ n\ \ (1\leq n\leq 10^5)--接下来的比赛场数

第三行包含\ n\个整数\ a_{1},a_{2},…,a_{n}(-100\leq a_{i}\leq 4000)\--每场比赛的表现分

输出描述:

输出一个整数--小R可能达到的最大分数
示例1

输入

复制 
1600
5
2000 1900 1800 1100 1500

输出

复制 
1850

说明

选择第一场和第二场参加最后达到的分数最高
第一场比赛后分数变为1600+⌊(2000-1600)/2⌋=1800
第二场比赛后分数变为1800+⌊(1900-1800)/2⌋=1850
可以证明没有其他选择方法可以达到更高的分数
示例2

输入

复制 
2000
6
1501 -52 1330 1909 1999 1245

输出

复制 
2000

说明

可以证明一局都不打是最好的选择