← 返回题目列表

Codeforces · 1912/A

A. 蓄能器顶点

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

Allyn 正在玩一款名为“Accumulator Apex”的新策略游戏。在这个游戏中,Allyn 被赋予一个整数 $$$x$$$ 的初始值(称为累加器)和 $$$k$$$ 整数列表。艾琳可以进行多次转弯。在每一轮中,如果生成的 $$$x$$$ 为非负数,Allyn 可以从任何非空列表中取出最左边的元素,并将其添加到累加器 $$$x$$$ 中。艾琳可以随时结束游戏。游戏的目标是获得累加器 $$$x$$$ 的最大可能值。请帮助 Allyn 找到他们在这个游戏中可以获得的累加器 $$$x$$$ 的最大可能值。

输入

输入的第一行包含两个整数 $$$x$$$ 和 $$$k$$$ ($$$0 \leq x \leq 10^9, 1 \leq k \leq 10^5$$$) - 累加器 $$$x$$$ 的初始值和列表的数量。接下来的 $$$k$$$ 行包含列表的描述:一个整数 $$$l_i$$$ ($$$l_i \ge 1$$$) 在同一行中按从左到右的顺序跟随列表的 $$$l_i$$$ 元素。列表中每个元素的绝对值不超过$$$10^9$$$,并且所有列表的总大小不超过$$$10^5$$$。

输出

输出的唯一行应包含 Allyn 可以获得的累加器 $$$x$$$ 的最大值。

示例

输入
复制

1 3
2 -1 2
2 -2 3
2 -3 4

输出
复制

4

输入
复制

1 2
3 -1 -1 4
4 1 -3 -4 8

输出
复制

4

注意

在第一个输入中,我们从 $$$x = 1$$$ 开始。然后,我们可以从第一个列表中取出第一个整数并得到 $$$x = 0$$$ — 添加第一个列表中的下一个整数 $$$2$$$,我们得到 $$$x = 2$$$。之后,我们可以将第二个列表中的整数相加,得到 $$$x = 3$$$。最后,我们可以将第三个列表中的整数相加,得到 $$$x = 4$$$。

在第二个输入中,我们可以添加第二个列表中的第一个整数并得到 $$$x = 2$$$。然后,通过添加第一个列表中的元素,我们得到 $$$x = 4$$$。我们无法添加更多整数来增加$$$x$$$。