Minimum Moves with Wind

Given the starting coordinates \( (x_s, y_s) \) and the destination coordinates \( (x_f, y_f) \) on a 2D Cartesian coordinate system (with the positive \(x\)-axis pointing east and the positive \(y\)-axis pointing north), and a sequence of \(T\) wind directions provided as a string (each character is one of E, S, W, or N), you are allowed to take an action at each time step: either move 1 unit in the direction of the wind or stay in place.

Your task is to determine the minimum number of moves (i.e. the number of times you actually move) needed to reach the destination by taking advantage of the wind. If it is impossible to reach the destination with the given wind sequence, output \( -1 \).

The wind directions affect your displacement as follows:

• E: move east (i.e. \( +1 \) in \(x\))
• W: move west (i.e. \( -1 \) in \(x\))
• N: move north (i.e. \( +1 \) in \(y\))
• S: move south (i.e. \( -1 \) in \(y\))

Note: You may choose to ignore a wind even if it is beneficial. The goal is to minimize the number of actual moves taken such that the cumulative moves exactly cover the displacement from \( (x_s, y_s) \) to \( (x_f, y_f) \). The minimal moves required will be the sum of the required units in each direction if it is possible to match them against the wind directions (in order).

inputFormat

The first line contains four integers \( x_s \), \( y_s \), \( x_f \), \( y_f \) separated by spaces.

The second line contains an integer \( T \) representing the number of time steps.

The third line contains a string of length \( T \) consisting of the characters E, S, W, and N, which represent the wind direction at each time step.

outputFormat

Output a single integer: the minimum number of moves needed to reach the destination. If it is impossible to reach the destination with the provided wind directions, output \( -1 \).

sample

0 0 2 -1
4
ESSE

3