누적기 Apex

시간 제한3초메모리 제한2048 MB

요약

시작값 x와 k개의 리스트가 주어지면, 각 리스트의 앞에서부터 원소를 꺼내 x에 더하고 x가 음수가 되지 않도록 하면서 최종 x의 최댓값을 구합니다.

난이도: 어려움10점 중 8점
유형: 그리디, 동적 계획법, 정렬
정답자: 아직 제출이 없습니다

문제

Allyn은 'Accumulator Apex'라는 새로운 전략 게임을 하고 있다. 이 게임에서 Allyn은 누적기(accumulator)라 부르는 정수 $x$ 의 초기값과 $k$ 개의 정수 리스트를 받는다. Allyn은 여러 턴을 진행할 수 있다. 각 턴에서 Allyn은 비어 있지 않은 리스트 하나를 골라 가장 왼쪽 원소를 꺼내 누적기 $x$ 에 더할 수 있다. 단, 더한 결과 $x$ 가 0 이상이어야 한다. Allyn은 게임을 언제든지 끝낼 수 있다. 목표는 누적기 $x$ 의 값을 가능한 한 크게 만드는 것이다. Allyn이 얻을 수 있는 $x$ 의 최댓값을 구하라.

입력

첫 줄에 누적기의 초기값 $x$ 와 리스트의 개수 $k$ 가 공백으로 구분되어 주어진다 ( $0 \leq x \leq 10^9$ , $1 \leq k \leq 10^5$ ). 다음 $k$ 개 줄에 리스트가 하나씩 주어진다. 각 줄은 정수 $l_i$ ( $l_i \ge 1$ )로 시작하고, 같은 줄에 왼쪽에서 오른쪽 순서로 $l_i$ 개의 원소가 이어진다. 각 원소의 절댓값은 $10^9$ 을 넘지 않으며, 모든 리스트의 전체 크기 합은 $10^5$ 을 넘지 않는다.

출력

Allyn이 얻을 수 있는 누적기 $x$ 의 최댓값을 한 줄에 출력한다.

힌트

첫 번째 입력에서 $x$ 는 1에서 시작한다. Allyn은 첫 번째 리스트의 첫 정수를 꺼내 $x = 0$ 을 만들고, 같은 리스트의 다음 정수 2를 더해 $x = 2$ 를 만든다. 이어서 두 번째 리스트의 정수를 더해 $x = 3$ 을, 세 번째 리스트의 정수를 더해 $x = 4$ 를 얻는다. 두 번째 입력에서는 두 번째 리스트의 첫 정수를 더해 $x = 2$ 를 얻고, 첫 번째 리스트의 원소를 더해 $x = 4$ 를 얻는다. 더 이상 정수를 더해 $x$ 를 늘릴 수 없다.

예제2

예제 1
입력
```
1 3
2 -1 2
2 -2 3
2 -3 4
```
예상 출력
```
4
```
예제 2
입력
```
1 2
3 -1 -1 4
4 1 -3 -4 8
```
예상 출력
```
4
```