Image Recognition

Irene works for Novel Efforts in Effective Recognition of Characters (NEERC). Her new project concerns image recognition using robots.

She starts with a very simple model. There are $d$ fixed images, called digits $0$ to $d - 1$. Each image is a $w \times h$ rectangle of white and black unit squares (pixels). All images are distinct (every two images differ in at least one pixel).

A robot is placed on the upper-left pixel of one of the images and runs a program written in the language below. Its task is to recognize which of the $d$ images it was placed on.

The programming language consists of the following commands:

• U, D, L, R --- movement commands. The robot moves one pixel up, down, left, or right. If a movement would take the robot outside the image, the task fails.
• ($\langle subprogram_w \rangle$:$\langle subprogram_b \rangle$) --- conditional. The robot checks the color of the pixel beneath it. If it is white then $\langle subprogram_w \rangle$ runs, otherwise $\langle subprogram_b \rangle$ runs.
• 0, 1, ..., 9 --- recognition commands. The robot executes one of these once it knows which image it is on; the program then terminates.

Each movement command takes one time unit. Conditionals and recognition commands are instantaneous.

A program is correct if, whenever the robot is placed on the image of digit $i$, execution ends with the command i. Among all correct programs, consider the one whose worst-case execution time --- the maximum number of movement commands executed over the $d$ possible starting images --- is as small as possible. Determine this minimal possible worst-case execution time.

The first line contains three integers $d$, $h$, and $w$ ($1 \le d \le 10$; $1 \le h, w \le 10$) --- the number of images, and the height and width of each image.

The rest of the input contains $d$ image descriptions. Each description has $h$ lines of length $w$, where every character is B (black) or W (white). Descriptions are given in order from image $0$ to image $d - 1$ and are separated by a single empty line.

Print a single integer: the minimal possible worst-case execution time of a correct recognition program.

The figure shows three example images that the robot must distinguish.