2016년 국제정보올림피아드는 러시아에서 열린다.
러시아 국기는 가로 띠 세 개로 나뉜다. 맨 윗줄은 흰색, 가운데 줄은 파란색, 맨 아랫줄은 빨간색이다.
선생님이 N×M 격자판을 가져왔다. 격자판의 각 칸은 흰색, 파란색, 빨간색 중 하나로 칠해져 있다. 이 격자판을 러시아 국기 모양으로 바꾸는 것이 과제다.
규칙은 다음과 같다.
- 칸 하나를 골라 원하는 색으로 다시 칠할 수 있다.
- 다 칠하고 나면 위쪽 부분은 전부 흰색, 가운데 부분은 전부 파란색, 아래쪽 부분은 전부 빨간색이어야 한다. 세 부분은 각각 한 줄 이상을 차지한다.
- 다시 칠하는 칸의 수는 최소여야 한다.
규칙을 지키면서 러시아 국기 모양으로 만들 때 다시 칠해야 하는 칸의 최소 개수를 구하는 프로그램을 작성하시오.