로마 숫자 걷기

N x N 정사각형 격자가 주어진다. 각 칸은 비어 있거나 로마 숫자 문자 I, V, X, L, C, D 중 하나를 담고 있다. 이 문자의 값은 각각 1, 5, 10, 50, 100, 500이다.

N은 홀수이고, 가운데 칸은 항상 비어 있다. 가운데 칸에서 시작해 한 번에 위, 아래, 왼쪽, 오른쪽으로 인접한 칸 하나로 이동한다. 가운데 칸을 떠난 뒤 방문한 문자들은 1부터 시작하는 연속된 양의 정수들의 로마 숫자 표기를 차례대로 이루어야 한다. 각 정수의 표기 뒤에는 마지막 정수까지 포함해 구분자 역할을 하는 빈 칸을 정확히 하나 방문해야 한다.

가능한 한 긴 수열을 만드는 것이 목표이다. 그런 수열에 포함될 수 있는 마지막 정수의 최댓값을 출력하라.

10진수를 이 로마 숫자 표기로 바꿀 때는 각 자릿수를 높은 자리부터 낮은 자리 순서로 따로 변환한 뒤 이어 붙인다. 예를 들어 726 = 700 + 20 + 6은 DCCXXVI가 된다. 이 문제에서 사용하는 감산 표기는 IV, IX, XL, XC, CD이며, 따라서 499 = 400 + 90 + 9는 CDXCIX가 된다.

첫째 줄에 홀수인 정수 N (1 <= N <= 99)이 주어진다.

다음 N개 줄에는 정사각형 격자의 한 행을 나타내는 N개의 문자가 주어진다. 각 문자는 I, V, X, L, C, D, . 중 하나이다. 점은 빈 칸을 뜻한다.

만들 수 있는 가장 긴 수열에서 마지막 수를 10진수로 한 줄에 출력한다.