조합 자물쇠

Gael은 조합 자물쇠가 달린 자물쇠를 가지고 있다. 각 자리마다 회전판이 하나씩 왼쪽에서 오른쪽으로 놓인 일반적인 조합 자물쇠와 달리, Gael의 조합 자물쇠에는 R개의 행(1번부터 R번)과 C개의 열(1번부터 C번)로 이루어진 R × C개의 회전판이 있다. 편의상 i번째 행과 j번째 열에 있는 회전판을 회전판 (i, j)라 하자.

일반적인 조합 자물쇠와 마찬가지로 Gael의 자물쇠에 있는 각 회전판에는 0부터 9까지 번호가 붙은 10개의 기호가 있고, 어느 순간이든 그중 하나가 Gael에게 보인다.

한 번의 연산으로 Gael은 R × C개의 회전판 중 하나를 골라 시계 방향으로 1/10바퀴 회전시킬 수 있다. 그러면 Gael에게 보이던 기호가 9가 아니었을 경우 보이는 기호가 1만큼 커지고, 9였을 경우 0으로 바뀐다.

일반적인 조합 자물쇠에서는 자물쇠를 열려면 각 회전판을 정확히 알맞은 만큼 회전시켜 미리 정해진 기호가 보이게 해야 한다. 그러나 Gael의 자물쇠는 기계적으로 마법이 걸려 있어 다르게 동작한다.

Gael의 자물쇠는 현재 기호 m을 보이는 회전판의 집합이 알파벳 L 모양을 이룰 때 열린다. 정확히는, 기호 m과 정수 x, y, δx, δy (0 ≤ m ≤ 9; 1 ≤ x − δx < x ≤ R; 1 ≤ y < y + δy ≤ C)가 존재하여 다음 중 적어도 하나가 참인 (i, j)에 대해서만 회전판 (i, j)이 기호 m을 보일 때 자물쇠가 열린다.

• i = x이고 y ≤ j ≤ y + δy
• x − δx ≤ i ≤ x이고 j = y

현재 회전판 (i, j)에 보이는 기호는 Si,j이다. Gael이 자물쇠를 여는 데 필요한 최소 연산 횟수를 구하도록 도와주자.

입력은 두 정수 R C (2 ≤ R, C ≤ 1000)로 시작한다. R은 Gael의 조합 자물쇠의 행 개수, C는 열 개수이다. 다음 R개의 줄 각각에는 0부터 9까지의 문자 C개로 이루어진 문자열 Si가 주어지며, 이는 회전판에 현재 보이는 기호를 나타낸다. i번째 줄의 j번째 문자가 Si,j의 값이다.

Gael의 자물쇠를 여는 데 필요한 최소 연산 횟수를 나타내는 정수를 한 줄에 출력한다.