25568번 - 피라미드

문제

삼각형 모양의 블록 피라미드를 가지고 노는 아기 팬더

3ドル$가지 색상의 블록으로 이루어진 블록 피라미드가 있다. 피라미드는 $N$행으로 이루어져 있고, $i\ (1 \le i \le N)$행은 $i$개의 블록으로 이루어져 있다.

또한, $i$행의 $j$번째 블록을 $(i, j)$로 표현했을 때, $(i, j)$는 아래와 같은 조건에 의해 최대 6ドル$개의 다른 블록과 맞닿아 있다.

• $i \ge 2$ 이고 $j \ge 2$ 라면, $(i - 1, j - 1)$와 맞닿아 있다.
• $i \ge 2$ 이고 $j \le i - 1$ 라면, $(i - 1, j)$와 맞닿아 있다.
• $j \ge 2$ 라면, $(i, j - 1)$와 맞닿아 있다.
• $j \le i - 1$ 라면, $(i, j + 1)$와 맞닿아 있다.
• $i \le N - 1$ 라면, $(i + 1, j),ドル $(i + 1, j + 1)$와 맞닿아 있다.

당신은 아름다운 블록 피라미드를 만들기 위해, 피라미드의 맞닿아 있는 블록의 색상이 같은 경우가 없도록 블록들을 재배치하고 싶다. 당신이 할 수 있는 연산은 아래 한 가지 뿐이다.

• $i\ (2 \le i \le N)$행의 블록 2ドル$개를 골라 교환한다.

이 때, 목표를 이루기 위한 연산 사용 횟수의 최솟값을 출력하라.

입력

첫 번째 줄에 정수 $N$이 주어진다. $(1 \le N \le 1,000円)$

두 번째 줄부터 $N$개의 줄에 걸쳐 블록 피라미드의 각 행의 상태가 주어진다. $i + 1$번째 줄에는 블록 피라미드의 $i$행을 이루는 블록 $i$개의 색상 정보가 공백을 사이에 두고 주어진다. 색상 정보는 0ドル,ドル 1ドル$ 또는 2ドル$의 정수이며, 각각 3ドル$가지의 다른 색상을 표현한다.

출력

피라미드의 맞닿아 있는 블록의 색깔이 같은 경우가 없도록 하기 위한 연산 사용 횟수의 최솟값을 출력하라. 해당 연산만으로 목표를 이루는 것이 불가능하다면 -1을 출력하라.

제한

힌트