Electronic Road Pricing (ERP)

The city of Eropagnis charges a car every time it changes direction. Every car carries a device that tells apart going straight, turning left, turning right and making a u-turn, and the driver is billed for what the device records. A left turn costs $1, a right turn costs $5, and going straight is free. A u-turn is forbidden, except at the end of a road where the car can no longer go forward, turn left or turn right. Such a u-turn costs $10 each time.

Every road in Eropagnis runs north, south, east or west, so the map fits on a grid. Write the guidance system that reports the cost of the cheapest route from the starting point to the finish point.

The map is a grid of characters. A # is a road segment and a . is not a road segment. The starting point and the finish point both sit on road segments, and every road segment can be driven in both directions.

The car always sits on one road segment and faces one of the four directions. From there it does exactly one of these four things.

• Go straight. If the segment ahead is a road, the car drives onto it. This is free and the direction stays the same.
• Turn left. If the segment to the left is a road, the car drives onto it and now faces that direction. This costs $1.
• Turn right. If the segment to the right is a road, the car drives onto it and now faces that direction. This costs $5.
• Make a u-turn. This is allowed only when the segments ahead, to the left and to the right are all non-road. The car turns around onto the segment behind it and pays $10.

A turn always moves the car onto the road it turns into, so the car cannot turn twice on one segment.

The height of the map is at least 4 and at most 30. The width of the map is at least 4 and at most 30. There is exactly one starting point and one finish point, and a route from the starting point to the finish point always exists. A frame of . surrounds the map, so the car can never leave the map that is given.

The input consists of the following lines.

1. The first line contains two positive integers, the height h and the width w of the map.

2. Each of the following h lines contains w characters. Each character is one of

   • . for a non-road part of the map,
   • # for a road part of the map,
   • E for the starting point with the car facing east,
   • W for the starting point with the car facing west,
   • N for the starting point with the car facing north,
   • S for the starting point with the car facing south,
   • F for the finish point.

Exactly one of the characters in the map is E, W, N or S. The top of the map is north and the right of the map is east.

Print a single number, the cost of the cheapest route from the starting point to the finish point.