Description

美好的日子总是短暂的。就像美貌的女孩总会被大魔王抢走
MM与No.57只谈了一半的人生，就被破门而入的大魔王打断了！！！
原来火柴西施MM的照片红遍网络，一不小心就被宅在星星的大魔王看到了，大魔王为了凸显存在感二话不说直接来到火星抢走了MM。
叔叔可以忍，婶婶不能忍，No.57决定要去星星打败大魔王抢回MM。
不过火星到星星的路途遥远，No.57必须要造艘飞船才好上路，
时间紧迫，那么现在马上出发找零件吧！
No.57从杂货店买来一张n * m的地图，地图上每个位置有E、W、S、O四种字符。
E 代表空地，No.57可以随意走入该方格
W 代表墙壁，No.57不能飞檐走壁所以不能进入该方格
S 代表飞船零件，No.57可以随意走入这个方格，走入该空格就可以拿走零件，也可以不拿走零件，拿走零件后该空格变成空地
O 代表充电站，No.57可以随意走入这个方格，走入该空格可以选择充电或者不充，但是一旦选择充电该空格就会变成空地
机器人No.57随身携带一个电池作为动力来源，电池容量是固定的，而他现在在(sx, sy)点1<=sx<=n,1<=sy<=m，保证起点不在墙上和充电站上，因为No.57心情急切
来到(sx, sy)点的时候电池已经耗尽。No.57每一步只能向上下左右四个方向走但不能走出地图，而且每走一步需要消耗1格电量，不过到达充电站可以充满电池，只
有移动才会消耗电量，当电池电量耗尽就不能再移动了。只有集齐地图上所有零件才能造出飞船，去追击大魔王夺回MM。保证零件数量加上充电站数量不超过15个。
显而易见No.57能行动多久电池的容量至关重要，那这次要能使No.57成功造出飞船电池容量至少为多少呢？

Input

第一行n, m, sx, sy四个数1<=n,m<=10,1<=sx<=n,1<=sy<=m
接下去n行，每行m个字符，表示地图内容，保证地图只包含E、W、S、O四种字符。

Output

输出一行。表示可以成功造出飞船所需携带电池的最小容量，若不可能造出飞船则输出-1。

Sample Input

7 7 7 7
SWEEEEE
WWEEEEE
OEWWEEE
EEEEWEE
EEEEEWE
EEEEEWE
EEEEEEE

Sample Output

-1

HINT

Source

信息学院第七届程序设计竞赛