게이머

아마 알고 있겠지만, 부쿠레슈티의 거리와 교차로는 완벽한 격자를 이룬다. 아마 모르고 있겠지만, 이 교차로마다 정확히 하나의 게임 클럽과 정확히 한 명의 게이머가 있다. 이상하게도 각 게임 클럽은 정확히 하나의 게임만 제공한다. 게이머들도 조금 이상하지만, 대체로 다음 규칙에 따라 단순한 삶을 산다.

1. 게이머는 절대로 자신이 있는 교차로의 클럽에서는 게임을 하지 않는다. 절대로!
2. 하루 동안 각 게이머는, 규칙 1에 어긋나지 않는 한, 모든 게임을 한 번씩 해야 한다.
3. 게이머는 오직 가로 또는 세로 방향으로만 한 교차로에서 다른 교차로로 이동한다.
4. 게이머는 한 클럽에서 다른 클럽으로 곧바로 갈 수 없다. 반드시 집으로 돌아와 무언가를 먹은 뒤에 가야 하며, 하루를 자신의 교차로에서 마쳐야 한다.
5. 게이머는 최적으로 살아야 하므로, 위 규칙들을 지키면서 게임할 시간을 충분히 확보하도록 항상 가능한 한 최선의 전략을 택한다.

모든 게이머가 동일하다는 점을 감안하여, 컴퓨터 마니아 협회는 전체 비게임 노력을 최소화하도록 도시를 최적화하기로 했다. 한 게이머의 비게임 노력이란 그 게이머가 하루 동안 지나가는 교차로의 수이다. 전체 비게임 노력은 도시의 모든 게이머의 비게임 노력을 합한 값이다. 이 최적화를 수행하기 위해, 협회는 주어진 도시 설명에 대해 전체 비게임 노력을 계산하는 프로그램이 필요하다.

표준 입력으로 여러 개의 도시 설명이 주어진다. 각 설명은 두 정수 $R$과 $C$ ($1 \le R, C \le 1000$)가 적힌 줄로 시작하며, 이는 도시의 교차로가 이루는 행의 수와 열의 수를 나타낸다. 이어서 $R$개의 줄이 주어지고 각 줄은 $C$개의 문자로 이루어지며, 각 교차로의 클럽이 제공하는 게임의 종류를 나타낸다. 각 게임은 한 자리 숫자 문자(0부터 9까지)로 표현된다.

각 도시 설명에 대해, 프로그램은 표준 출력의 한 줄에 정수 하나 — 그 도시의 전체 비게임 노력 — 를 출력한다.

첫 번째 경우, 네 명의 게이머는 각각 게임 1과 2를 해야 한다. 다행히 둘 다 한 교차로 거리에 있어, 각 게이머의 비게임 노력은 4이다 (집에서 클럽 1로, 클럽 1에서 집으로, 집에서 클럽 2로, 클럽 2에서 집으로). 따라서 전체 비게임 노력은 16이다.

두 번째 경우, 아홉 명의 게이머는 각각 게임 두 개는 한 교차로 거리에, 하나는 두 교차로 거리에 두고 있어, 전체 비게임 노력은 $9 \times (1+1+1+1+2+2) = 72$이다.