310940: CF1912A. Accumulator Apex

A. Accumulator Apextime limit per test3 secondsmemory limit per test1024 megabytesinputstandard inputoutputstandard output

Allyn is playing a new strategy game called "Accumulator Apex". In this game, Allyn is given the initial value of an integer $x$, referred to as the accumulator, and $k$ lists of integers. Allyn can make multiple turns. On each turn, Allyn can withdraw the leftmost element from any non-empty list and add it to the accumulator $x$ if the resulting $x$ is non-negative. Allyn can end the game at any moment. The goal of the game is to get the largest possible value of the accumulator $x$. Please help Allyn find the largest possible value of the accumulator $x$ they can get in this game.

Input

The first line of the input contains two integers $x$ and $k$ ($0 \leq x \leq 10^9, 1 \leq k \leq 10^5$) — the initial value of the accumulator $x$ and the number of lists. The next $k$ lines contain the description of lists: an integer $l_i$ ($l_i \ge 1$) followed on the same line by $l_i$ elements of the list in the order from left to right. Each element of lists does not exceed $10^9$ by the absolute value, and the total size of all lists does not exceed $10^5$.

Output

The sole line of the output should contain the largest value of the accumulator $x$ Allyn can get.

ExamplesInput

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

Output

4

Input

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

Output

4

Note

In the first input, we start with $x = 1$. Then, we can take the first integer from the first list and get $x = 0$ — adding the next integer $2$ from the first list we get $x = 2$. After that, we can add the integers from the second list and obtain $x = 3$. Finally, we can add the integers from the third list and obtain $x = 4$.

In the second input, we can add the first integer from the second list and get $x = 2$. Then, by adding the elements from the first list, we get $x = 4$. We cannot add more integers to increase $x$.

题目大意：
阿林正在玩一款名为 "Accumulator Apex" 的新策略游戏。在这个游戏中，给定一个整数 \( x \) 作为累加器的初始值，以及 \( k \) 个整数列表。阿林可以进行多个回合，每个回合，如果从某个非空列表的最左边取出一个元素并加到累加器 \( x \) 上后 \( x \) 仍然非负，则可以执行该操作。阿林可以随时结束游戏。游戏的目标是使累加器 \( x \) 的值尽可能大。请帮助阿林找到在这个游戏中可以得到的累加器 \( 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 \)。

输出数据格式：
输出应该包含一个单独的行，内容是阿林可以得到的累加器 \( x \) 的最大值。

例子：
输入：
```
1 3
2 -1 2
2 -2 3
2 -3 4
```
输出：
```
4
```

注意：
在第一个输入中，我们从 \( x = 1 \) 开始。然后，我们可以从第一个列表中取出第一个整数得到 \( x = 0 \)，再加入第一个列表的下一个整数 \( 2 \) 得到 \( x = 2 \)。之后，我们可以加上第二个列表的整数得到 \( x = 3 \)。最后，我们可以加上第三个列表的整数得到 \( x = 4 \)。

在第二个输入中，我们可以加上第二个列表的第一个整数得到 \( x = 2 \)。然后，通过加上第一个列表的元素，我们得到 \( x = 4 \)。我们不能再添加整数来增加 \( x \)。题目大意： 阿林正在玩一款名为 "Accumulator Apex" 的新策略游戏。在这个游戏中，给定一个整数 \( x \) 作为累加器的初始值，以及 \( k \) 个整数列表。阿林可以进行多个回合，每个回合，如果从某个非空列表的最左边取出一个元素并加到累加器 \( x \) 上后 \( x \) 仍然非负，则可以执行该操作。阿林可以随时结束游戏。游戏的目标是使累加器 \( x \) 的值尽可能大。请帮助阿林找到在这个游戏中可以得到的累加器 \( 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 \)。 输出数据格式： 输出应该包含一个单独的行，内容是阿林可以得到的累加器 \( x \) 的最大值。 例子： 输入： ``` 1 3 2 -1 2 2 -2 3 2 -3 4 ``` 输出： ``` 4 ``` 注意： 在第一个输入中，我们从 \( x = 1 \) 开始。然后，我们可以从第一个列表中取出第一个整数得到 \( x = 0 \)，再加入第一个列表的下一个整数 \( 2 \) 得到 \( x = 2 \)。之后，我们可以加上第二个列表的整数得到 \( x = 3 \)。最后，我们可以加上第三个列表的整数得到 \( x = 4 \)。 在第二个输入中，我们可以加上第二个列表的第一个整数得到 \( x = 2 \)。然后，通过加上第一个列表的元素，我们得到 \( x = 4 \)。我们不能再添加整数来增加 \( x \)。