8112689 - 东南西北

给出起点和终点的坐标及接下来T个时刻的风向(东南西北),每次可以选择顺风偏移1个单位或者停在原地。求到达终点的最少时间。

如果无法偏移至终点,输出“-1”。

输入

第一行两个正整数x1,y1,表示小明所在位置。

第二行两个正整数x2,y2,表示小明想去的位置。

第三行一个整数T,表示T个时刻。

第四至第N+3行,每行一个字符,表示风向,即东南西北的英文单词的首字母。

输出

最少走多少步。

样例

输入

1 1
2 2
5
E
N
W
W
N

输出

2

输入

1 1
2 2
1
W

输出

-1

输入

1 1
2 2
3
W
W
W

输出

-1

提示

样例1:向东走一步,向北走一步。

样例2、3:无法到达。

1<=T<=50

东:East

南:South

西:West

北:North

时间限制 1 秒
内存限制 128 MB
讨论 统计
上一题 下一题