东南西北

题目描述

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

输入输出格式

输入格式


第一行两个正整数x1,y1,表示小明所在位置。 第二行两个正整数x2,y2,表示小明想去的位置。 第三行一个整数T,表示T个时刻。 第四至第N+3行,每行一个字符,表示风向,即东南西北的英文单词的首字母。

输出格式


最少走多少步。

输入输出样例

输入样例 #1

1 1
2 2
5
E
N
W
W
N

输出样例 #1

2

输入样例 #2

1 1
2 2
1
W

输出样例 #2

-1

输入样例 #3

1 1
2 2
3
W
W
W

输出样例 #3

-1

说明

样例1:向东走一步,向南走一步。 样例2、3:无法到达。 1<=T<=50 东:East 南:South 西:West 北:North