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

输入格式

输入的第一行包含两个整数 $x$ 和 $k$ ($0 \le x \le 10^9, 1 \le k \le 10^5$)，分别表示累加器 $x$ 的初始值和列表的数量。接下来的 $k$ 行包含列表的描述：一个整数 $l_i$ ($l_i \ge 1$)，随后在同一行给出该列表从左到右的 $l_i$ 个元素。列表中每个元素的绝对值不超过 $10^9$，且所有列表的总大小不超过 $10^5$。

输出格式

输出仅一行，包含 Allyn 能得到的累加器 $x$ 的最大值。

样例

输入 1

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

输出 1

4

输入 2

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

输出 2

4

说明

在第一个样例中，我们从 $x = 1$ 开始。然后，我们可以从第一个列表中取出第一个整数，得到 $x = 0$；接着加上第一个列表中的下一个整数 $2$，得到 $x = 2$。之后，我们可以加上第二个列表中的整数，得到 $x = 3$。最后，我们可以加上第三个列表中的整数，得到 $x = 4$。

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