城市街道交费系统最近创立了。一辆汽车左转一次需付费1，右转一次需付费5。只有当前进、左转、右转都无路可走的时候，调头才是允许的，调头每次付费10。
给出一张城市地图，要求你求出从起始点到达终止点的花费最少的路径。幸运的是，所有的道路都是正北、正南、正西或正东方向的。

第一行有两个整数，地图高度h和宽度w。
其后h行，每行w个字符，将是以下字符中的一个：
. 表示障碍区。
# 表示道路。
E 表示起始点且汽车面朝东。
W 表示起始点且汽车面朝西。
N 表示起始点且汽车面朝北。
S 表示起始点且汽车面朝南。
F 表示终点。

仅包含一个整数，即为最便宜路径的费用。

样例一解释：
直走，然后左转3次，最后右转到终止点F。如果先直走然后右转2次，花费将是10。
样例二解释：
最便宜的路径花费7：立刻左转，直走，在第一个岔路口左转，随后右转。
对于100% 的数据：4≤h,w≤30。
数据保证地图中只有一个起点，一个终点，他们之间存在着可通达的路径。同时保证地图最外层一圈都是障碍。