超级英雄与怪物战斗。战斗由多个回合组成,每回合持续 $$$n$$$ 分钟。一轮结束后,下一轮立即开始。这一次又一次地重复。
每轮都有相同的场景。它由 $$$n$$$ 数字序列描述:$$$d_1, d_2, \dots, d_n$$$ ($$$-10^6 \le d_i \le 10^6$$$)。第 $$$i$$$ 个元素意味着怪物的 hp(生命值)在每轮的第 $$$i$$$ 分钟内改变值 $$$d_i$$$。正式来说,如果在一轮的第 $$$i$$$ 分钟之前怪物的生命值是 $$$h$$$,那么在第 $$$i$$$ 分钟之后它会变为 $$$h := h + d_i$$$。
怪物的初始生命值为$$$H$$$。这意味着在战斗之前怪物有$$$H$$$生命值。打印怪物死亡后的第一分钟。如果怪物的生命值小于或等于$$$0$$$,怪物就会死亡。如果战斗无限继续,则输出-1。
输入
第一行包含两个整数 $$$H$$$ 和 $$$n$$$ ($$$1 \le H \le 10^{12}$$$, $$$1 \le n \le 2\cdot10^5$$$)。第二行包含整数序列 $$$d_1, d_2, \dots, d_n$$$ ($$$-10^6 \le d_i \le 10^6$$$),其中 $$$d_i$$$ 是在一轮的第 $$$i$$$ 分钟内改变怪物生命值的值。
输出
如果超级英雄无法杀死怪物,则打印-1,并且战斗将无限持续。否则,打印正整数 $$$k$$$,使得 $$$k$$$ 是怪物死亡后的第一分钟。
示例
输入 #1
1000 6 -100 -200 -300 125 77 -4
输出 #1
9
输入 #2
1000000000000 5 -1 0 0 0 0
输出 #2
4999999999996
输入 #3
10 4 -3 -6 5 4
输出 #3
-1