Roman Numeral Walk

Time limit1sMemory limit128 MB

Summary

Find the longest path from the grid center through empty-separated cells that spells consecutive Roman numerals starting at 1, and print the last number reached.

Level: Hard8 of 10
Topics: DFS, Backtracking, String, Simulation
Solved: No attempts yet

Problem

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.

Input

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.

Output

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

Examples3

Example 1
Input
```
3
I.I
I.V
I..
```
Expected output
```
6
```
Example 2
Input
```
5
.IV.I
II.II
XV.VI
..I..
...II
```
Expected output
```
11
```

Example 3

Input

7
IIXV.LX
XL.IXVI
.IVIX.X
LIX.VIX
X.XIXI.
LIVL.XX
VI.XIXL

Expected output