꽃길

2017년 4월 5일 식목일, 진아는 나무 대신 하이테크관 앞 화단에 꽃을 심어서 등교할 때마다 꽃길을 걷고 싶었다.

진아가 가진 꽃씨는 심은 지 정확히 1년 뒤에 꽃이 피므로, 진아는 다음 해 식목일부터 꽃길을 걸을 수 있다.

진아에게는 꽃씨가 세 개밖에 없다. 그래서 세 꽃이 하나도 죽지 않고 1년 뒤에 모두 활짝 피기를 바란다.

화단은 $N \times N$ 격자 모양이고, 진아는 $(1,1)$부터 $(N,N)$까지의 칸 중 한 곳에 씨앗을 심을 수 있다. 씨앗은 그림 (a)처럼 한 칸에 심고, 1년 뒤 꽃이 피면 그림 (b)처럼 된다. 즉 핀 꽃은 씨앗을 심은 칸(꽃술)과 그 칸의 위, 아래, 왼쪽, 오른쪽 칸(꽃잎)까지 모두 5칸을 차지한다.

꽃을 심을 때 주의할 점이 있다. 꽃이 핀 뒤 한 꽃의 꽃잎이나 꽃술이 다른 꽃의 꽃잎이나 꽃술과 같은 칸에 겹치면 두 꽃 모두 죽는다. 또 꽃잎이 화단 밖으로 나가면 그 꽃은 죽는다.

그림 (c)는 세 꽃이 정상적으로 핀 모습이고, 그림 (d)는 두 꽃이 죽은 모습이다.

하이테크관 앞 화단은 격자의 칸마다 대여 가격이 다르다. 진아는 서로 다른 세 씨앗을 모두 꽃피우면서 가장 싼 가격에 화단을 빌리고 싶다.

단, 화단은 꽃이 핀 모양을 기준으로 빌려야 하므로 꽃 하나당 5칸의 땅을 빌려야 한다.

돈이 많지 않은 진아를 위해, 꽃을 심는 데 필요한 최소 비용을 구해 보자.

첫째 줄에 화단의 한 변의 길이 $N$ ($6 \le N \le 10$)이 주어진다.

다음 $N$개의 줄에는 각 줄마다 $N$개씩, 화단의 칸별 대여 가격 $G$ ($0 \le G \le 200$)가 공백으로 구분되어 주어진다.

세 꽃을 모두 피우기 위한 최소 비용을 출력한다.