### Problem Statement

Billy is going to his grandmother's house. To help him do that, his mother has written down a detailed list of instructions for him to follow. Each instruction is a character 'N', 'S', 'W' or 'E', telling him to go exactly 1 block to the north, south, west or east, respectively. Billy's city consists of an infinitely large grid of streets, where each street extends infinitely to both sides, and the space between 2 adjacent streets going in the same direction is always 1 block. Billy's house and his grandmother's house are both located at street corners in this city.

Billy knows that his mother does not always choose the shortest path. Therefore, he wants to make a new list of instructions that will also lead him to his grandmother's house, but uses the minimum possible number of instructions.

You will be given inst, a String with the original list made by Billy's mom. Return the new list Billy wants. If there are several solutions, return the one that comes first alphabetically.

### Definition

 Class: OptimalList Method: optimize Parameters: String Returns: String Method signature: String optimize(String inst) (be sure your method is public)

### Constraints

-inst will contain between 1 and 50 characters, inclusive.
-Each character of inst will be either 'N', 'S', 'W' or 'E'.

### Examples

0)

 `"NENENNWWWWWS"`
`Returns: "NNNWWW"`
1)

 `"NNEESSWW"`
`Returns: ""`
 Billy's grandmother lives in the same place as him, so he can get there without walking the big roundabout path his mother suggests.
2)

 `"NEWSNWESWESSEWSENSEWSEWESEWWEWEEWESSSWWWWWW"`
`Returns: "SSSSSSSSWWW"`
3)

 `"NENENE"`
`Returns: "EEENNN"`
 The list is already optimal in the number of instructions, but Billy wants the alphabetically first optimal list.

#### Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=7752

#### Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10672&pm=7752

soul-net

#### Testers:

PabloGilberto , brett1479 , Cosmin.ro , Olexiy

#### Problem categories:

Greedy, Simulation