Origin of Life

Conway's Game of Life is not really a game but a cellular automaton: a set of rules describing how adjacent cells on a grid interact. Here we work on a rectangular grid with $m$ rows and $n$ columns, and each cell is identified by its integer coordinates.

The game advances in discrete steps: from the current generation a next generation is computed. In every generation each cell is either live or dead. A cell's state in the next generation depends only on the states of its immediate neighbours in the current generation. Two distinct cells $(x_1, y_1)$ and $(x_2, y_2)$ are immediate neighbours when $|x_1 - x_2| \le 1$ and $|y_1 - y_2| \le 1$; that is, cells that are horizontally, vertically, or diagonally adjacent. A cell not on the border therefore has eight neighbours.

Three integer parameters $a$, $b$, $c$ control the transition rules:

• A live cell with fewer than $a$ live neighbours dies of loneliness (dead in the next generation).
• A live cell with more than $b$ live neighbours dies of overcrowding (dead in the next generation).
• A dead cell with more than $c$ live neighbours is born (live in the next generation).
• Otherwise a cell keeps its current state.

Applying the rules repeatedly may eventually repeat a generation (life continues forever) or wipe out every cell. Looking backwards instead, some generation may have no possible predecessor at all — no configuration could produce it in one step. Such a generation is called a Garden of Eden.

Given the parameters and the current generation, decide whether its history could have started at a Garden of Eden. If it could, print the smallest number of steps needed to reach the current generation from a Garden of Eden. If the current generation is itself a Garden of Eden the answer is $0$. If no Garden of Eden leads to the current generation, print -1.

Print a single integer.

The first line contains five space-separated integers $m$, $n$, $a$, $b$, and $c$ with $1 \le m \le 4$, $1 \le n \le 5$, $1 \le a < b \le 8$, and $1 \le c \le 8$.

Each of the next $m$ lines contains a string of $n$ characters describing one row of the current generation. A * marks a live cell and a . marks a dead cell.