Magical Labyrinth

The magical labyrinth is a rectangular grid with H rows and W columns (0 < H < 100, 0 < W < 100). Each cell in the grid contains either a zero or a one. Zeros represent free cells, while ones represent walls. The labyrinth is magical because the contents of the cells change every second. Initially, during the first second, every cell contains a one. The content of each cell changes according to its unique period a: for the first (a–1) seconds, the cell contains a 1, then for the next second, it contains a 0, followed by another (a–1) seconds of 1, then another second of 0, and so forth. The period a is unique for each cell and satisfies 1 < a < 24.

A path in the labyrinth is defined as a sequence of cells, each containing a zero, where each pair of consecutive cells shares a side.

Your task is to determine the smallest positive t such that during the t-th second, the following two conditions are met:

1. The cells at positions (1, 1) and (H, W) both contain zeros.

2. There exists a path in the labyrinth connecting these two cells.

Input

The first line of the input contains the natural numbers H and W.

Each of the next H lines contains W numbers: the j-th number in the k-th row specifies the period a for the cell located at the j-th column and k-th row.

Output

The output should be a single integer — the desired t. If no such t exists, the output should be zero.

Note: In example 3, the content of the magical labyrinth changes as follows:

Examples