Description

Allyn 正在玩一款名为 Accumulator Apex 的新策略游戏。在游戏中，Allyn 会获得一个整数 $x$ 的初始值（称为累加器）和 $k$ 个整数列表。Allyn 可以进行多轮操作。在每一轮中，Allyn 可以从任意一个非空列表中取出最左侧的元素，并将其加到累加器 $x$ 中，前提是操作后的 $x$ 为非负数。Allyn 可以随时结束游戏。游戏的目标是让累加器 $x$ 的值尽可能大。请帮助 Allyn 找出他们在这场游戏中能获得的最大累加器值 $x$。

Input Format

输入的第一行包含两个整数 $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$。

Output Format

输出的唯一一行应包含 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

Hint

在第一个输入样例中，初始时 $x = 1$。我们可以从第一个列表中取出第一个整数，得到 $x = 0$——接着从第一个列表中取出下一个整数 $2$，得到 $x = 2$。之后，我们可以从第二个列表中取出整数，得到 $x = 3$。最后，从第三个列表中取出整数，得到 $x = 4$。

在第二个输入样例中，我们可以从第二个列表中取出第一个整数，得到 $x = 2$。然后，从第一个列表中取出元素，得到 $x = 4$。此时无法再通过添加更多整数来增加 $x$ 的值。

翻译由 DeepSeek V3 完成