26074번 - 곰곰이와 테트리스

문제

곰곰이와 총총이가 재미있는 테트리스 게임을 하려고 한다.

테트리스 게임은 세로 $N$칸, 가로 $M$칸인 빈 직사각형 게임판에서 시작한다.

곰곰이부터 돌아가면서 원하는 테트리스 블록 혹은 1×1블록을 빈 공간에 하나씩 배치한다.

단, 이때 블록을 회전시켜서 배치할 수 있으나 뒤집는 것은 불가능하고, 기존 블록과 겹치지 않고 격자와 테두리를 벗어나지 않게 배치해야 한다.

[그림 1] 배치할 수 있는 블록의 종류와 번호

각 플레이어는 블록을 배치할 때마다 블록의 종류마다 정해진 점수를 얻는다.

게임을 진행하다 게임판에 더 이상 블록을 배치할 수 없게 되면 게임은 종료되고, 자신의 최종 점수로 승패를 겨루게 된다.

동점을 방지하기 위해, 곰곰이는 선공 페널티로 자신의 최종 점수에서 0.5점을 빼게 된다.

두 등장인물이 최적의 방법으로 게임을 진행했을 때, 마지막에 점수가 높은 등장인물이 누구인지 출력하자.

테트리스 블록과 1×1블록은 종류마다 개수가 무한히 있기 때문에 블록이 떨어지는 경우는 없다고 가정한다.

입력

첫째 줄에 게임판의 크기 $N, M\ (1 \leq N, M \leq 20)$이 주어진다.

둘째 줄에 [그림 1]에 표시된 번호에 해당하는 블록의 점수 8개 $(1 \leq P_1, \cdots, P_8 \leq 1\ 000)$가 차례대로 주어진다.

입력은 모두 양의 정수로 주어진다.

출력

곰곰이가 이기는 경우에는 GomGom, 총총이가 이기는 경우에는 ChongChong을 출력한다.

제한

힌트