남우는 우후죽순으로 자라 있는 나무들을 잘 정리하여 정원을 가꾸려고 합니다. 정원은 n × n 격자 모양으로 이루어져 있으며, 각 칸에는 하나의 나무가 심어져 있습니다. 상하좌우로 맞닿아 있는 경우를 인접한 경우라고 했을 때, 남우는 최대 4번 인접해 있는 두 나무를 묶는 것을 진행하려고 합니다. 이때 묶은 나무끼리는 서로 겹쳐서는 안 되며, 두 나무가 묶였을 때 얻을 수 있는 아름다움은 두 나무의 키의 합과 동일하다고 합니다. 이러한 상황에서 묶인 쌍의 아름다움의 합을 최대로 만들어보려고 합니다.

예를 들어 n = 4 일 때 다음과 같이 정원 정보가 주어진 경우를 생각해보겠습니다. 각 격자 칸에 적혀있는 숫자는 각 칸에 있는 나무들의 키를 의미합니다.

이때 다음과 같이 나무들을 묶게 되면 서로 묶은 쌍끼리 겹치지 않되 얻을 수 있는 아름다움의 합이 25(=7+6+7+5)로 최대가 됩니다.

초기 격자의 상태가 주어졌을 때 최대 4개의 쌍을 겹치지 않게 잘 골라 얻을 수 있는 아름다움의 총 합을 최대로 하는 프로그램을 작성해보세요.

본 문제의 저작권은 (주)브랜치앤바운드에 있으며, 저작자의 동의 없이 무단 전재/복제/배포를 금지합니다.