Description

Given the coordinates of the start and end points, and the wind direction (east, south, west, north) at each of the next $T$ time steps, you may either move $1$ unit with the wind or stay in place at each time step. Find the minimum number of moves needed to reach the destination.

The coordinate system is the Cartesian plane, where the positive $x$-axis points east and the positive $y$-axis points north.

If it is impossible to reach the destination, output $-1$.

Input Format

The first line contains two positive integers $x_1, y_1$, representing Xiaoming’s current position.

The second line contains two positive integers $x_2, y_2$, representing the position Xiaoming wants to reach.

The third line contains an integer $T$, representing $T$ time steps.

From line $4$ to line $T+3$, each line contains one character representing the wind direction, i.e., the first letter of the English words for east ($\verb!E!$), south ($\verb!S!$), west ($\verb!W!$), and north ($\verb!N!$).

Output Format

Output a single integer, the minimum number of moves.

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

Hint

Sample Explanation

• Sample $1$: Move one step east, then one step north.
• Samples $2$ and $3$: Impossible to reach.

Constraints

For all testdata, $1 \le T \le 50$.

Translated by ChatGPT 5