Mikroskil Robotic Club (MiRC) is a fun club for robotics enthusiast where the members often come up with strange yet interesting ideas. Their dream is to build an intelligent humanoid robot which can replace them in semesters' exams.
To join MiRC, you have to solve a certain simple problem. Let there be a cartesian grid where a robot is placed at its origin (0, 0). The robot has the ability to accept and execute several commands:
With this movement system, each coordinate can actually be represented as a set of robot's movement. For example,
Let string S represents the robot's movement which corresponds to a coordinate (x, y). Your task is to determine the length of the shortest string which also corresponds to the same coordinate (x, y). As you can see from the examples above, NNEEES and EENEEEWW correspond to the same coordinate (3, 1), and NNEEES is shorter with the length of 6. However, the shortest possible string which corresponds to coordinate (3, 1) has the length of 4, i.e. any of NEEE, ENEE, EENE, EEEN.
MiRC wants to filter applicants who cannot solve this simple problem (i.e. those who just want to cling to MiRC famous name). We find this problem interesting, thus, we set this for IdeaFuse 2018 Qualification Round. Write a program to solve this problem and prove that you are a better coder.
Input contains a string S (1 ≤ S ≤ 1,000) in a single line. String S represents the robot's movements and consists of only characters N, S, E, and W. The meaning of each character can be found in the problem statement.
Output in a line an integer representing the output for the given input.
|This is the example given in the problem statement.|
|The given input already has the shortest length possible.|
|One example: NNWNNW|
|Empty string (length = 0) also produces the same coordinate, (0, 0).|
End of Problem