cho.sh

Red Rover

Given a route string over N, S, E, W of length at most 100, find the minimum total length of a message using one optional macro M and its definition that expands to the route.

Medium6Dynamic programmingStringNo attempts yetTime limit2sMemory limit512 MB

Problem

One of the older Mars rovers has nearly finished its tour of duty and is waiting for one last set of instructions to explore the Martian surface. The survey team has already picked the route, and transmitting the final instructions to the rover is your job. The route is a sequence of moves in the four cardinal directions: north, south, east, and west. Each move is sent as one character: N, S, E, or W.

Power is the problem. Every received signal drains the rover's battery, and the charge left is already dangerously low. The rover's builders planned for routes with a lot of repetition, so you may optionally define a single macro.

A message that uses the macro consists of two strings. The first string is over the characters N, S, E, W, M, and it lists moves together with calls to the macro (M). The second string is over N, S, E, W, and it defines what M expands to. For example,

WNMWMME
EEN

encodes the route

WNEENWEENEENE

The version with the macro takes only 10 characters, while sending the original route takes 13.

The transmission cost is the total number of characters sent, that is, the sum of the lengths of the two strings. If you do not use a macro, you send the route as it is and the cost equals the length of the route. Given a route, find the minimum number of characters needed to transmit it.

Input

The first line contains the route to transmit to the rover. The route is a string over the letters N, S, E, and W, and its length is between 1 and 100, inclusive.

Output

Print the minimum number of characters needed to encode the route.