우유 도시

영학이는 딸기우유, 초코우유, 바나나우유를 좋아한다. 입맛이 까다로워서 마시는 순서를 스스로 정해 두었다.

1. 맨 처음에는 딸기우유를 한 팩 마신다.
2. 딸기우유를 마신 다음에는 초코우유를 한 팩 마신다.
3. 초코우유를 마신 다음에는 바나나우유를 한 팩 마신다.
4. 바나나우유를 마신 다음에는 다시 딸기우유를 한 팩 마신다.

우유 여행을 떠난 영학이는 우유 가게로 가득한 도시에 도착했다. 이 도시는 한 변이 $N$인 정사각형 격자이고, 칸마다 우유 가게가 하나씩 있다. 각 가게는 딸기우유, 초코우유, 바나나우유 중 한 종류만 판다.

영학이는 북서쪽 끝 칸 $(1, 1)$에서 출발해 남동쪽 끝 칸 $(N, N)$까지 간다. 한 번에 동쪽이나 남쪽으로 한 칸씩만 움직이므로 이미 지나친 가게로 되돌아가지 않는다. 지나는 칸마다 그 가게의 우유를 한 팩 사 마시거나 그냥 지나친다. 마시는 순서 규칙은 항상 지키며, 한 칸에서 두 팩 이상 마시지는 않는다. 출발 칸과 도착 칸에서도 우유를 마신다.

영학이가 마실 수 있는 우유의 최대 개수를 구하여라.

첫째 줄에 도시의 한 변 길이 $N$이 주어진다. ($1 \le N \le 1000$)

둘째 줄부터 $N$개의 줄에 걸쳐 도시의 정보가 주어진다. 각 줄에는 $N$개의 정수가 공백으로 구분되어 주어진다. 0은 딸기우유를 파는 가게, 1은 초코우유를 파는 가게, 2는 바나나우유를 파는 가게를 뜻한다. 0, 1, 2 외의 정수는 주어지지 않는다.

영학이가 마실 수 있는 우유의 최대 개수를 출력한다.