2048 (어려움)

2048은 $4 \times 4$ 보드에서 혼자 하는 게임이다. 이 링크에서 직접 해볼 수 있다.

한 번의 이동은 보드 위의 모든 블록을 위, 아래, 왼쪽, 오른쪽 중 한 방향으로 끝까지 미는 것이다. 이때 같은 값을 가진 두 블록이 부딪히면 값이 두 배인 블록 하나로 합쳐진다. 한 번의 이동에서 이미 합쳐진 블록은 다시 합쳐지지 않는다. 실제 게임에서는 이동할 때마다 블록이 하나씩 생기지만, 이 문제에서는 블록이 새로 생기지 않는다.

그림 1	그림 2	그림 3

그림 1에서 블록을 위로 이동시키면 그림 2가 된다. 여기서 왼쪽으로 이동시키면 그림 3이 된다.

그림 4	그림 5	그림 6	그림 7

그림 4에서 블록을 오른쪽으로 이동시키면 그림 5가 되고, 다시 위로 이동시키면 그림 6이 된다. 여기서 오른쪽으로 이동시키면 그림 7이 된다.

그림 8	그림 9

그림 8에서 블록을 왼쪽으로 옮기면 2 두 개가 부딪혀 4로 합쳐지고, 그림 9가 된다.

그림 10	그림 11	그림 12	그림 13

그림 10에서 위로 이동시키면 그림 11이 된다.

그림 12에서 위로 이동시키면 그림 13이 된다. 한 번의 이동에서 이미 합쳐진 블록은 또 합쳐지지 않기 때문이다.

그림 14	그림 15

같은 수가 한 줄에 세 개 있으면 이동하는 방향에 가까운 두 블록이 먼저 합쳐진다. 위로 이동시키는 경우에는 위쪽 두 블록이 먼저 합쳐진다. 그림 14에서 위로 이동시키면 그림 15가 된다.

이 문제에서 다루는 2048의 보드 크기는 $N \times N$이다. 보드의 크기와 블록의 초기 상태가 주어졌을 때, 최대 10번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

첫째 줄에 보드의 크기 $N$ ($1 \le N \le 20$)이 주어진다. 둘째 줄부터 $N$개의 줄에 보드의 초기 상태가 한 줄에 $N$개씩 주어진다. 0은 빈 칸이고, 나머지 값은 모두 블록이다. 블록에 적힌 수는 2 이상 1024 이하인 2의 거듭제곱이다. 블록은 적어도 하나 주어진다.

최대 10번 이동시켜서 얻을 수 있는 가장 큰 블록의 값을 출력한다.