# 城市街道交通费系统

## 题目描述

城市街道交费系统最近创立了。一辆汽车左转一次需付费 $1$ ，右转一次需付费 $5$ 。只有当前进、左转、右转都无路可走的时候，调头才是允许的，调头每次付费 $10$ 。

给出一张城市地图，要求你求出从起始点到达终止点的花费最少的路径。幸运的是，所有的道路都是正北、正南、正西或正东方向的。

## 输入格式

输入格式如下：

1. 第一行有两个整数，地图高度 $h$ 和宽度 $w$。
2. 其后 $h$ 行，每行 $w$ 个字符，将是以下字符中的一个：

- `.` 表示障碍区。
- `#` 表示道路。
- `E` 表示起始点且汽车面朝东。
- `W` 表示起始点且汽车面朝西。
- `N` 表示起始点且汽车面朝北。
- `S` 表示起始点且汽车面朝南。
- `F` 表示终点。

## 输出格式

仅包含一个整数，即为最便宜路径的费用。

## 样例 #1

### 样例输入 #1

```
8 11
...........
....#####..
....#...#..
....#...#..
.#E######..
....#......
.##F#......
...........
```

### 样例输出 #1

```
8
```

## 样例 #2

### 样例输入 #2

```
17 21
.....................
.#######.............
.#.....#.......#.....
.###...#.......#.....
...#...#.......#.....
.###...#.......#.....
.#.....#.......#.....
.############F#####..
.......#..........#..
.......#..........#..
...#...#...#####..#..
...#...#...#.#.#..#..
..#S########.#.#..#..
...#.......#.###..#..
...#.......#......#..
...........########..
.....................
```

### 样例输出 #2

```
7
```

## 提示

样例一解释：

直走，然后左转 $3$ 次，最后右转到终止点 `F`。如果先直走然后右转 $2$ 次，花费将是 $10$ 。

---

样例二解释：

最便宜的路径花费 $7$ ：立刻左转，直走，在第一个岔路口左转，随后右转。

---

对于 $100\%$ 的数据：$4 \leq h,w \leq 30$。

数据保证地图中只有一个起点，一个终点，他们之间存在着可通达的路径。同时保证地图最外层一圈都是障碍。