2048 (Easy)

2048은 $4 \times 4$ 크기의 보드에서 혼자 하는 퍼즐 게임이다.

한 번의 이동은 보드 위의 모든 블록을 상, 하, 좌, 우 네 방향 중 한 방향으로 미는 것이다. 값이 같은 두 블록이 부딪히면 두 블록은 값이 두 배인 블록 하나로 합쳐진다. 한 번의 이동에서 이미 합쳐진 블록은 그 이동 동안 다시 합쳐지지 않는다. 원래 게임에서는 이동할 때마다 블록이 새로 생기지만, 이 문제에서는 블록이 새로 생기지 않는다.

그림 1	그림 2	그림 3

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

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

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

그림 8	그림 9

그림 8에서 왼쪽으로 이동시키면 2 두 개가 부딪혀 4로 합쳐지고, 그림 9가 된다.

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

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

그림 14	그림 15

값이 같은 블록이 세 개 연달아 놓여 있으면 이동하는 방향에 더 가까운 두 블록이 먼저 합쳐진다. 위로 이동하면 위쪽 두 블록이 합쳐진다. 그림 14에서 위로 이동하면 그림 15가 된다.

이 문제에서 다루는 2048 게임은 보드의 크기가 $N \times N$이다. 보드의 크기와 블록의 초기 배치가 주어지면, 최대 5번 이동해서 만들 수 있는 가장 큰 블록의 값을 구하는 프로그램을 작성하시오.

첫째 줄에 보드의 크기 $N$이 주어진다. ($1 \le N \le 20$)

둘째 줄부터 $N$개의 줄에 보드의 초기 상태가 한 줄에 $N$개씩 주어진다. 0은 빈 칸이고, 0이 아닌 값은 블록이다. 블록에 쓰여 있는 수는 2 이상 1024 이하인 2의 거듭제곱이다. 블록은 적어도 하나 주어진다.

최대 5번 이동시켜 얻을 수 있는 가장 큰 블록의 값을 출력한다. 한 번도 이동하지 않는 경우도 허용하므로, 답은 처음 보드에 있는 가장 큰 블록의 값보다 작을 수 없다.