We have arrived at the age of the Internet. Many software applications have transformed from stand-alone to online applications. Computer games are following this trend as well. Online games are becoming more and more popular, not only because they are more intelligent, but also because they can bring great profits. "The computer game industry is developing rapidly in China. Online game revenues amounted to 1.3 billion Yuan last year and are expected to reach 6.7 billion Yuan by 2007." reported by China Daily in 2004.
However, good games originate from good programmers. We take for example that there is a RPG (Role Playing Game) and your boss asks you to implement some tasks. For simplicity's sake, we assume there are two kinds of roles in this game: one is player and the other is monster. You should help the player to achieve the goal: reach the place where treasure is positioned as early as possible and get the treasure.
The map of the game is a matrix of N * M identical cells. Some cells are passable blocks, and others are non-passable rocks. At any time, there is at most one role occupying a block. At the beginning, the time is set to 0, and the player is at a certain block. He then moves towards the treasure. At each turn, we have some rules:
1) The player can stay in the same block during the next one-second time duration, or he can walk or run towards the east, south, west, north, northeast, northwest, southeast, and southwest.
2) With walking, the player can arrive at the corresponding passable blocks around him (See Fig.1). Each move takes 1 second.
3) With running, the player can arrive at the corresponding passable blocks 2 cells away from him (See Fig.2). Each run takes 1 second. As demonstrated in Fig.3, if a neighbor cell is not passable, the player cannot run in that direction. For example, if cell 2 is a rock, running from 1 to 3 is impossible.
4) The monsters are classified into aggressive and non-aggressive. If a monster occupies a cell, the player cannot move into that cell or run through that cell. In addition, the player cannot move into the cells surrounding an aggressive monster, because it will attack the player near it. For example, in Fig.4, if there is an aggressive monster in 5, then the cell 1, 2, 3, 4, 6, 7, 8 and 9 are in its attacking region, so the player cannot stay in or pass through these cells.
5) Monsters change their positions each turn. Each monster appears by its position sequence iteratively. That's to say, given the position sequence of monster i: (x1, y1), (x2, y2), ..., (xs, ys), its initial position is (x1, y1) at time 0, then it appears in (x2, y2) at time 1, and so on. When monster i arrives at (xs, ys) at time s-1, it will arrive in (x1, y1) at time s, and start to repeat.
At the start of each turn, all the monsters change their positions first (the way of changing is given above). If a monster appears in the player's cell, or if an aggressive monster appears near the player to put him in its attacking region, the player will die, and the goal cannot be achieved. After all the monsters change their positions, the player makes a move or stays in the same cell. In his move, the moving path should not be occupied by any rocks or monsters or in the attacking region of any aggressive monsters. When counting the total time, we can neglect the time between monsters' position change and the player's move. Given the map of the game, the player's starting position, the treasure position and all the monsters' positions in every second, your task is to write a program to find the minimum time that the player gets the treasure.