← 返回题目列表

Codeforces · 1141/E

E. 超级英雄之战

中文机器翻译题面 查看原题

超级英雄与怪物战斗。战斗由多个回合组成,每回合持续 $$$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