A Broken Door

There is a rectangular maze made of square rooms arranged in a grid. The maze is surrounded by walls except at its entry and exit. The entry is the open upper side of the top-left room, and the exit is the open lower side of the bottom-right room.

Between every pair of horizontally or vertically adjacent rooms there is a wall. Each such wall either holds a door with a card-key lock or has no door at all. Inserting a card into a door opens it and lets you pass through; the door closes again immediately, and the card is not returned. Any card opens any door. You cannot pass through a wall that has no door.

Given a maze, it is easy to compute how many cards are needed to walk from the entry to the exit: each door you pass costs one card. In the maze of Figure G-1 you can reach the exit with ten cards by following the green arrows () shown in Figure G-2.

Figure G-1: A map of a maze

Figure G-2: One of the shortest paths

Now suppose that exactly one of the doors is broken and cannot be passed, but you do not know which one. If you insert a card into the broken door, the card is returned immediately and the door does not open. A broken door looks exactly like a working one, so you cannot recognize it in advance.

Figure G-3: A maze that potentially can't be passed through

If the door marked with a red X () in Figure G-3 is broken, there is no way to get from the entry to the exit. In the maze of Figure G-1, however, you can always reach the exit no matter which single door is broken. Suppose you set out along the shortest path of Figure G-2 and discover that the door marked with a red X in Figure G-4 is broken. You might then follow the green arrows, using twenty cards in total.

Figure G-4: A maze with a broken door

You can do better. Follow the path in Figure G-5 until you discover the broken door. This path is not the shortest one — it needs at least twelve cards — but once you find a broken door on it, you switch to the shortest path to the exit that avoids that door. With this strategy you can always get through with sixteen cards, whichever door is broken. Figure G-6 shows one of the worst cases of the strategy; it also needs sixteen cards.

Figure G-5: The path before you find the broken door

Figure G-6: One of the worst cases of the strategy

Write a program that, for a given maze, prints the minimum number of cards that guarantees passing from the entry to the exit no matter which single door turns out to be broken.

The input consists of one or more datasets, each describing a maze. There are at most 100 datasets.

The first line of a dataset contains two integers, the height h and the width w of the maze, in this order (2 ≤ h, w ≤ 30). The next 2 × h − 1 lines describe where the doors are. These lines alternate between horizontal walls and vertical walls:

• A line describing horizontal walls (the 1st, 3rd, 5th, … of the 2 × h − 1 lines) begins with a leading space and then lists w − 1 integers separated by spaces. The c-th integer describes the wall between the c-th and (c+1)-th rooms of that row.
• A line describing vertical walls (the 2nd, 4th, … of them) begins without a leading space and lists w integers separated by spaces. The c-th integer describes the wall between the two vertically adjacent rooms in column c.

In every case, an integer 0 means the wall has a door, and 1 means the wall is solid (no door).

The end of the input is indicated by a line containing two zeros.

For each dataset, print a single line containing one integer: the minimum number of cards that guarantees reaching the exit whichever single door is broken. If there is a door whose breakage makes the exit unreachable, print −1 instead. The line must contain nothing but this number.