You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

给出起点和终点的坐标，及接下来 $T$ 个时刻的风向（东南西北），每个时刻可以选择顺风偏移 $1$ 个单位或者停在原地。求到达终点的最少移动步数。

坐标采用平面直角坐标系，$x$ 轴正向为东，$y$ 轴正向为北。

如果无法偏移至终点，输出 $-1$。

输入格式

第一行两个正整数 $x_1,y_1$，表示小明所在位置。

第二行两个正整数 $x_2,y_2$，表示小明想去的位置。

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

第四至第 $N+3$ 行，每行一个字符，表示风向，即东（$\verb!E!$）南（$\verb!S!$）西（$\verb!W!$）北（$\verb!N!$）的英文单词的首字母。

输出格式

一行一个整数，表示最少移动步数。

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\le T\le 50$。