#1113. zzj & liaoy 的大召唤术

内存限制:512 MiB 时间限制:750 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: JM233333

题目描述

眼看着wzk直冲着JM所在的房间而来,JM开始方了。他还有一线生机,克洛斯贝尔的地下水路是非常神奇的,在这些叶子节点房间中,存在着一个zzj & liaoy布置的神秘魔法阵,JM可以借此逃到其他房间去。

JM在墙上摸了半天,终于找到了zzj & liaoy的魔法祭坛。但是不巧的是,zzj & liaoy刚刚完成了他们精心准备的魔法仪式,即将召唤出一位强力队友。这个时候JM闯了进来,触发了zzj留下的保护装置,只有做出这道题才能冲破保护装置从而通过魔法阵逃跑:

“假如ACM选手每天实力会增长自己已有实力的 ,同时接下来 天每天会有一场训练,第 场训练会消耗 的实力。试问JM,你可知道能够遭得住这样的训练,并且中途和结束时实力值不会变成负数的选手,最少实力值需要是多少吗?”

JM太菜了不会做,他把你抓来帮他解决这个问题,如果你解决不了,他就会把你抓去喂qz。

输入格式

第一行包括两个整数 ,分别表示选手实力的增长,以及接下来训练的天数。

第二行包括 个整数,第 个整数表示

输出格式

输出一个整数,表示选手最少需要的实力值。

为了简化题目,第 天选手的实力值会先减少 ,然后增加 ,向下取整。注意,每天计算的时候都要向下取整。

样例

样例输入

100 3
10 10 10

样例输出

18

数据范围与提示

Hint

对于样例,每天结束时的实力值为:16,12,4