Manhattan Parcel Robot

Time limit1sMemory limit1024 MB

Summary

Given a string of N moves (N, E, S, W), find the fewest steps back to the warehouse, which is the Manhattan distance of the net displacement.

Level: Easy2 of 10
Topics: Simulation, Implementation
Solved: No attempts yet

Problem

A parcel robot operates in the Manhattan district of New York. The robot is quite large and can deliver several parcels to different destinations at once. After delivering all parcels, the robot must return to the warehouse to pick up new ones.

The streets of Manhattan form a grid. Every street runs exactly north-south or east-west. In addition, the distance between any two adjacent parallel streets is the same.

We call one step of the robot a move from one intersection along a street to the next intersection.

Find the minimum number of steps in which the robot can reach the warehouse.

Input

The first line contains the number $N$ of steps the robot has taken so far ( $1 \le N \le 1\,000$ ). The second line contains $N$ characters, each giving the direction of one step. N means north, E east, S south, and W west.

Output

Print one line with the minimum number of steps the robot needs to get back to the warehouse.

Examples2

Example 1
Input
```
5
NNEEE
```
Expected output
```
5
```
Example 2
Input
```
7
NNNSSWE
```
Expected output
```
1
```