# 문제 자율주행 기술의 발전과 함께 차량 내 인포테인먼트 기술 또한 많은 주목을 받고 있다. 최근 자동차 실내에는 디스플레이의 대형화를 비롯해 새로운 제어 기술이 빠르게 적용되고 있는데, 완전 자율주행 시대가 다가올 수록 이런 변화가 가속화될 전망이다. 개인 맞춤형 인포테인먼트 시스템 역시 핵심 기능 중 하나다. 자율주행 시대에 발맞춰 차량 내 디지털 시스템을 활용한 게임을 개발하고 있다.

게임의 룰은 가로 세로 $N$칸의 차고(격자)가 있고, 각 차고에는 색깔이 있는 자동차가 하나씩 있다. 한 턴에 한 칸을 선택하며, 선택한 칸과 상하좌우 칸에 들어있는 자동차의 색이 같다면 모두 사라진다. 그리고 사라진 칸들과 연결된 칸들의 상하좌우 칸에 들어있는 자동차의 색이 같다면 함께 사라진다. (문제 하단 예시 참고.) 이때, 획득할 수 있는 점수는 사라진 자동차의 개수와 사라지는 차고 칸을 모두 포함하는 가장 작은 직사각형의 넓이의 합이다. 자동차들이 사라지고 나면 위에 있는 자동차들이 아래로 떨어져 빈 칸을 채운다. 위쪽에는 충분한 자동차들이 더 있어서 위에서 추가적으로 떨어지며 모든 칸을 채운다. 위에서 어떤 자동차들이 떨어질지는 입력으로 주어진다. 위와 같은 게임을 3차례 반복 했을 때, 주어진 조건에서 얻을 수 있는 가장 큰 점수를 계산하라. # 입력 입력으로는 차고 격자 칸의 가로, 세로 길이인 $N$이 첫 줄에 주어진다. 다음 $3N$개의 줄에 $N$개의 자연수가 주어진다. 각 자연수는 차고 칸에 있는 자동차의 색상 번호이다. * $1 ≤ N ≤ 15$ * 색상 번호는 $1$ 이상 $10^9$이하의 자연수이다. # 출력 주어진 조건에서 게임을 3차례 시뮬레이션 했을 때 얻을 수 있는 가장 큰 점수를 출력한다. # 서브태스크 | 번호 | 배점 | 제한 | | ---- | ---- | --------- | | 1 | 20 | $N \le 4$ | | 2 | 80 | 다른 제약 조건이 없다. | # 노트

첫번째 예제를 보면, 시뮬레이션 1회차에 4번 색상의 차량을 가지고 있는 차고(격자)가 2곳이 있다. 사라지는 자동차의 개수(2점)와 해당 차고를 포함하는 가장 작은 직사각형 면적(2점)을 합한 4점을 획득한다. 시뮬레이션 2회차에서 3번 색상의 차량을 가지고 있는 차고가 2곳이 있다. 사라지는 자동차의 개수(2점)와 해당 차고를 포함하는 가장 작은 직사각형 면적(2점)을 합한 4점을 획득하여 총 8점 획득한다. 마지막으로, 시뮬레이션 3회차에서 1번 색상의 차량을 가지고 있는 차고가 3곳이 있다. 사라지는 자동차의 개수(3점)와 해당 차고를 포함하는 가장 작은 직사각형 면적(4점)을 합한 7점을 획득하여, 총 15점을 획득한다.

두번째 예제를 보면, 시뮬레이션 1회차에 2번 색상의 차량을 가지고 있는 차고가 6곳이 있다. 사라지는 자동차의 개수(6점)와 해당 차고를 포함하는 가장 작은 직사각형 면적(6점)을 합한 12점을 획득한다. 시뮬레이션 2회차에서 3번 색상의 차량을 가지고 있는 차고가 3곳이 있다. 사라지는 자동차의 개수(3점)와 해당 차고를 포함하는 가장 작은 직사각형의 면적(3점)을 합한 6점을 획득하여 총 18점 획득한다. 마지막으로, 시뮬레이션 3회차에서 1번 색상의 차량을 가지고 있는 차고가 9곳이 있다. 사라지는 자동차의 개수(9점)와 해당 차고를 포함하는 가장 작은 직사각형의 면적(9점)를 합한 18점을 획득하여, 총 36점을 획득한다. 만약 아래와 같이 시뮬레이션 2회차에서 1번 색상의 차량을 선택하는 경우, 사라지는 자동차의 개수(6점)와 해당 차고를 포함하는 가장 작은 직사각형의 면적(6점)을 합한 12점을 획득할 수 있으나, 시뮬레이션 3회차에서 사라지는 자동차의 개수(3점)과 해당 차고를 포함하는 가장 작은 직사각형의 면적(3점)으로 6점을 획득하여 총 30점을 획득하여 가장 큰 점수가 될 수 없다.