Roman Numeral Walk

An N x N square grid is given. Each cell is either empty or contains one Roman numeral character: I, V, X, L, C, or D, whose values are 1, 5, 10, 50, 100, and 500.

N is odd, and the center cell is empty. Starting from the center cell, walk through the grid by moving one cell up, down, left, or right at each step. After leaving the center, the visited characters must form Roman numerals for consecutive positive integers starting from 1. After each numeral, including the last one, the walk must visit exactly one empty cell as a separator.

The goal is to make the sequence as long as possible. Print the largest integer whose Roman numeral appears in such a sequence.

A decimal number is converted to this Roman notation by converting each decimal digit separately, from the largest place value to the smallest, and concatenating the results. For instance, 726 = 700 + 20 + 6 becomes DCCXXVI. The subtractive forms used here are IV, IX, XL, XC, and CD; therefore 499 = 400 + 90 + 9 becomes CDXCIX.

The first line contains an odd integer N (1 <= N <= 99).

Each of the next N lines contains N characters describing one row of the square. Each character is one of I, V, X, L, C, D, and .. A dot denotes an empty cell.

Print one line containing the decimal representation of the last number in the longest possible sequence.