문제

2048 게임은 $4\times 4$ 격자 위에서 즐기는 게임이다. 원본 게임은 여기서 플레이할 수 있다.

플레이어는 매 턴마다 상하좌우 중 한 방향으로 전체 타일을 움직일 수 있다. 이때 같은 값을 갖는 두 타일이 충돌하면 하나로 합쳐지게 된다. 다만, 한 번의 이동에서 이미 합쳐진 타일은 또 다른 타일과 합쳐질 수 없다. 매 이동 이후 무작위 빈 칸에 90%의 확률로 2가 적힌 타일이나 4가 적힌 타일이 생성되지만, 이 문제에서는 고려하지 않는다.

1번 그림에서 오른쪽으로 움직이면 2번 그림처럼 되고, 2번 그림에서 위쪽으로 움직이면 3번 그림처럼 된다.

1번 그림에서 왼쪽으로 이동하면 2번 그림처럼 된다. 움직이려는 방향 쪽의 타일들이 먼저 합쳐지기 때문이다.

1번 그림에서 아래쪽으로 이동하면 2번 그림처럼 된다. 한 번의 이동에서 이미 합쳐진 타일은 또 다른 타일과 합쳐질 수 없기 때문이다.

이 문제에서는 $4 \times 4$ 격자가 아니라 $N\times N$ 격자가 주어진다. 이 격자에서 최대 $10$번 움직였을 때 가능한 타일의 최댓값을 구해보자.

입력

첫째 줄에 $N$이 주어진다. ($2\le N\le 10$)

둘째 줄부터 $N$개의 줄에 걸쳐 격자의 초기 상태가 주어진다. $0$은 빈칸을 나타내고, 이외의 값은 모두 타일의 값을 나타낸다. 타일의 값은 $2$보다 크거나 같고 $1024$보다 작거나 같은 $2$의 제곱수이다.

출력

최대 $10$번 움직였을 때 가능한 타일의 최댓값을 출력한다.

예제 입력 1

3
4 0 0
2 0 0
0 0 2

예제 출력 1

8

예제 입력 2

10
4 16 2 4 0 0 2 16 0 2
32 0 2 16 0 4 4 2 0 2
4 8 4 0 4 32 0 8 0 4
0 2 0 4 2 0 4 0 2 0
2 32 2 4 2 2 2 32 0 4
8 0 8 0 4 8 8 4 16 8
32 32 2 0 2 4 0 4 16 2
2 2 4 0 0 0 0 4 2 4
4 8 4 0 2 0 2 2 0 2
2 2 4 2 4 4 16 8 4 4

예제 출력 2

256