Accumulator Apex

Time limit3sMemory limit2048 MB

Summary

Given a starting value x and k lists, take elements from the front of each list and add them to x, keeping x non-negative, to maximize the final x.

Level: Hard8 of 10
Topics: Greedy, Dynamic programming, Sorting
Solved: No attempts yet

Problem

Allyn is playing a new strategy game called "Accumulator Apex". In this game, Allyn is given the initial value of an integer $x$ , called 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$ , as long as the resulting $x$ is non-negative. Allyn can end the game at any moment. The goal is to get the largest possible value of the accumulator $x$ . Find the largest value of $x$ Allyn can reach.

Input

The first line contains two integers $x$ and $k$ ( $0 \leq x \leq 10^9$ , $1 \leq k \leq 10^5$ ), the initial value of the accumulator and the number of lists. The next $k$ lines describe the lists. Each line starts with an integer $l_i$ ( $l_i \ge 1$ ), followed on the same line by the $l_i$ elements of the list from left to right. Each element has an absolute value of at most $10^9$ , and the total size of all lists is at most $10^5$ .

Output

Print the largest value of the accumulator $x$ that Allyn can get, on a single line.

Hint

In the first input, $x$ starts at 1. Allyn takes the first integer from the first list to get $x = 0$ , then takes the next integer 2 from the same list to get $x = 2$ . After that, Allyn adds the integers from the second list to get $x = 3$ , and then the integers from the third list to get $x = 4$ . In the second input, Allyn adds the first integer from the second list to get $x = 2$ , then adds the elements of the first list to get $x = 4$ . No more integers can be added to increase $x$ .

Examples2

Example 1
Input
```
1 3
2 -1 2
2 -2 3
2 -3 4
```
Expected output
```
4
```
Example 2
Input
```
1 2
3 -1 -1 4
4 1 -3 -4 8
```
Expected output
```
4
```