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

第一行有两个整数，地图高度h和宽度w。 其后h行，每行w个字符，将是以下字符中的一个： . 表示障碍区。

表示道路。

E 表示起始点且汽车面朝东。 W 表示起始点且汽车面朝西。 N 表示起始点且汽车面朝北。 S 表示起始点且汽车面朝南。 F 表示终点。

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

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