Alea iacta est

문제

아이작 B. 맨프레드(Isaac B. Manfred)는 언제나 엄청난 부자가 되기를 꿈꿨다. 어릴 때는 장난감 대신 지폐를 가지고 놀았고, 고등학교를 마친 뒤에는 곧바로 유명 은행의 수석 브로커가 되었다. 경력과 함께 재산도 불어났지만, 금융 위기가 그의 삶을 송두리째 바꿔 놓았고, 잘나가던 브로커는 하루아침에 빈털터리가 되었다.

잃은 돈을 되찾기 위해 I.B.M.은 카지노에서 시간을 보낸다. 하지만 그는 대부분의 도박꾼과 달리 영리한 사람이라, 무작정 베팅하지 않고 각 게임을 연구해 이기고 지는 확률을 정확히 계산한다. 룰렛과 블랙잭을 포기한 그는 주사위 게임으로 눈을 돌렸는데, 그중 몇몇은 상표로 등록된 게임 Yahtzee! 와 비슷하다. 규칙은 조금씩 다르지만 기본 원리는 같으며, 아래는 그 단순화된 버전이다.

게임은 열한 번의 라운드로 이루어진다. 각 라운드에서 플레이어는 주사위 다섯 개를 굴린다. 첫 번째 굴림 뒤에는 원하는 주사위(하나도 남기지 않거나 전부 남겨도 된다)를 그대로 두고 나머지를 다시 굴릴 수 있으며, 다시 굴린 주사위는 세 번째이자 마지막으로 한 번 더 굴릴 수 있다. 최대 두 번의 재굴림을 마친 뒤, 플레이어는 현재의 주사위 다섯 개를 아래 조합 중 하나에 배정하고, 그에 따라 그 라운드의 점수가 정해진다.

조합	조건	점수 계산	예시	점수
Ones	1이 하나 이상.	1 하나당 1점.	1 1 2 4 5	2
Twos	2가 하나 이상.	2 하나당 2점.	1 2 2 2 6	6
Threes	3이 하나 이상.	3 하나당 3점.	1 2 4 5 5	0
Fours	4가 하나 이상.	4 하나당 4점.	4 4 4 4 4	20
Fives	5가 하나 이상.	5 하나당 5점.	1 2 3 4 5	5
Sixes	6이 하나 이상.	6 하나당 6점.	1 4 6 6 6	18
Sequence	(1 2 3 4 5) 또는 (2 3 4 5 6).	30점.	1 2 3 4 5	30
Full House	같은 값 세 개와 다른 값 두 개.	다섯 주사위의 합.	2 2 5 5 5	19
Four of a kind	같은 값 네 개와, 나머지 하나는 다른 값.	다섯 주사위의 합.	4 4 4 4 5	21
Five of a kind	다섯 개 모두 같은 값.	50점.	1 1 1 1 1	50
Chance	없음.	다섯 주사위의 합.	2 4 5 5 6	22

최종 주사위가 어떤 조합의 조건을 만족하지 못하더라도 그 조합에 배정할 수는 있으며, 이 경우 그 라운드는 0점이 된다.

예를 들어 플레이어가 2, 3, 6, 6, 5를 굴린 뒤 6 두 개를 남기고 나머지 세 개를 다시 굴려 1, 1, 6이 나왔다고 하자. 여기서 멈추면 Full House로 20점을 얻을 수 있다. 하지만 6이 하나 더 나오길 기대하며 1 두 개를 마지막으로 다시 굴려 4와 5가 나오면, Sixes로 18점 또는 Chance로 27점을 얻는다.

게임 전체에서 열한 개의 조합은 각각 정확히 한 번씩 사용해야 한다. 어떤 결과가 남은 어떤 조합에도 맞지 않더라도 플레이어는 그중 하나에 반드시 배정해야 하며, 그 라운드는 0점이 되고 그 조합은 더 이상 쓸 수 없게 된다. 그래서 조합이 몇 개 남지 않은 종반부일수록 게임이 까다로워진다.

아이작은 이 게임의 전자식 버전이 있는 카지노를 찾아냈고, 수많은 판을 지켜본 끝에 난수 생성기를 해독해 앞으로 나올 모든 주사위 눈을 정확히 예측할 수 있게 되었다. 그렇더라도 최적 전략을 찾는 일은 여전히 어렵다. 얻을 수 있는 최대 총점을 계산하는 프로그램을 작성하라.

입력

입력에는 여러 개의 시나리오가 각각 한 줄씩 주어진다. 각 줄에는 공백으로 구분된 세 정수 $A$, $C$, $X_0$이 있다. 이들은 난수 생성기를 정의한다. $A$는 곱수($1 \le A \le 2^{31}$), $C$는 증분($0 \le C \le 2^{31}$), $X_0$은 초기 시드($0 \le X_0 \le 2^{31}$)이다. 마지막 시나리오 다음 줄에는 0이 세 개 주어지며, 이 줄은 처리하지 않는다.

이 생성기는 선형 합동 생성기로, 다음 수는 이전 수로부터 아래와 같이 계산된다.

$$X_{n+1} = (A \cdot X_n + C) \bmod 2^{32}$$

즉 결과의 하위 32비트만 남긴다. 수열 $X_1, X_2, X_3, \dots$이 유사난수열을 이루며, 각 값이 주사위 한 번의 눈을 결정한다. 이런 생성기의 무작위성은 상위 비트에 있으므로, $n$번째 눈($n = 1$부터)은 $X_n$의 하위 16비트를 버리고 6으로 나눈 나머지를 구한 뒤 1을 더해 얻는다.

$$\operatorname{roll}(n) = \left(\left\lfloor X_n / 2^{16} \right\rfloor \bmod 6\right) + 1$$

이렇게 하면 1과 6 사이의 눈이 나온다. 예를 들어 $A = 69069$, $C = 5$, $X_0 = 0$이면 눈은 1, 6, 6, 3, 2, 4, 3, 2, 3, 5, 1, 6, 6, 4, 5, 1, 3, 4, 1, ... 순으로 나온다.

게임의 맨 처음 굴림에서 나오는 다섯 주사위는 $\operatorname{roll}(1), \dots, \operatorname{roll}(5)$이며, 주사위를 다시 굴릴 때마다 이 수열의 다음 값들을 순서대로 소비한다. 따라서 게임 전체가 사용하는 유사난수 값의 개수는 플레이어의 남기기/다시 굴리기 선택에 따라 달라진다.

출력

각 시나리오마다 정수 하나를 출력한다. 주어진 생성기로 진행되는 게임에서 얻을 수 있는 최대 총점이며, 이는 열한 라운드의 점수를 모두 더한 값이다.