2514. Ninja Legend

Ninjas are professional spies in the Middle Age of Japan. They have been popular in movies and games as they have been described with extraordinary physical abilities and unrealistic abilities.

You are absorbed in one of ninja games, Ninja Legend. In this game, you control in an exceptionally talented ninja named Master Ninja and accomplish various missions. In one of the missions, the ninja intrudes into a mansion and aims to steal as many gold pieces as possible. It is not easy to be done because there are many pitfalls to evade him. Once he falls into a pitfall, all he can do will be just to wait for being caught by the owner of this mansion. This definitely means failure of the mission. Thus, you must control the ninja with a good strategy.

The inside of mansion is represented by a grid map as illustrated below. Master Ninja enters at and exits from the entrance. He can move in the four directions to the floor cells. He can pick up gold blocks when he moves to the cells where they are placed, but it is also allowed to pick up them in the later visit of those cells or even to give up them.

The ninja has a couple of special abilities for dealing with the pitfalls. He has two moving modes: normal mode and dash mode. He is initially in the normal mode. He gets into the dash mode when he moves in the same direction by two cells in a row without picking up gold blocks. He gets back to the normal mode when he changes the direction, picks up a gold block, or runs on a wall as mentioned later. He is able to jump over a pitfall, or in the dash mode he can jump over two pitfalls in his dashing direction. In addition, when he is in the dash mode, he can run on a wall to pass over up to four pitfalls in his dashing direction. For his running, there must be consecutive wall cells adjacent to the passing cells including the departure and arrival floor cells. Note that he gets back to the normal mode when he runs on a wall as mentioned previously.

In the figure up, the figure 2 shows how the ninja runs on a wall, and the figure 3 illustrates a case in which he cannot skip over pitfalls by running on a wall.

You want to know the maximum number of gold blocks the ninja can get, and the minimum cost to get those gold blocks. So you have decided to write a program for it as a programmer. Here, move of the ninja from a cell to its adjacent cell is considered to take one unit of cost.