23815번 - 똥게임

이 게임은 똥냄새가 너무 나서 도저히 볼 수가 없다! 따라서 당신은 직접 똥게임을 하지 않고 프로그램한테 똥게임을 시킬 것이다. 처음에는 사람 1명으로 시작한다. 당신에게는 총 $N$번의 턴이 주어지며, 각 턴마다 다음 선택지 4개중 2개가 주어진다. 같은 선택지가 주어질 수도 있다. 각 선택지는 $+x, -x, *x, /x \, (1 \leq x \leq 9)$ 중 하나로 주어진다.

1. $+x$를 선택할 경우, 사람의 수가 $x$명만큼 증가한다.
2. $-x$를 선택할 경우, 사람의 수가 $x$명만큼 감소한다.
3. $*x$를 선택할 경우, 사람의 수가 $x$배가 된다.
4. $/x$를 선택할 경우, 사람의 수가 $x$만큼 나눠진다. 만약 현재 사람 수가 x로 나눠지지 않을 경우 나머지는 버린다.

$N$개의 선택지 중 1번에 한해 광고를 보고 선택지를 건너뛸 수 있다. 광고를 보지 않고 선택지를 건너뛰지 않아도 된다. 만약 각 턴이 끝난 뒤 현재 사람이 0명 이하가 되면 게임 오버가 된다. 당신은 $N$번의 선택지를 거친 후 사람의 수를 최대로 만들어야 한다. 어떠한 선택을 하더라도 중간에 사람의 수가 32비트 정수 범위를 넘지 않음을 보장한다.

첫 번째 줄에 선택지의 개수 $N \, (1 \leq N \leq 100,000)$가 주어진다. 

그 이후 $N$개의 줄에 걸쳐 2개의 선택지가 공백을 사이로 두고 주어진다.

각 선택지는 $+x, -x, *x, /x$ 중 하나로 주어진다 ($1 \leq x \leq 9$).

$N$개의 선택지를 거친 후 최대 사람의 수를 출력한다. 

만약 어떤 선택을 하더라도 게임 오버가 된다면 ddong game을 출력한다.

첫번째 예제에서는 $+5$, $*2$를 선택하고 3번째 선택지를 건너뛸 경우, 12명으로 최대가 된다.

두번째 예제에서는 어떤 선택지를 고르더라도 게임 오버가 된다.