OpenKattis
Saudi IOI: Intensive Selection Contest 2 (Recursion+Dynamic Programming)

Start

2019-01-03 12:15 CET

Saudi IOI: Intensive Selection Contest 2 (Recursion+Dynamic Programming)

End

2019-01-03 16:00 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -2160 days 19:23:33

Time elapsed

3:45:00

Time remaining

0:00:00

Problem B
Going to School

\includegraphics[width=0.8\textwidth ]{skolvag.png}
Figure 1: The dotted line shows Cissi’s optimal path in the first example.

Cissi is walking from her home to school, following a long street going from the west to the east. On her way, she passes a number of street crossings where the crossing street either goes north (N), south (S) or both (B). At every street crossing, there are crosswalks on both the crossing streets and the main street (see the figure above), and she can only cross the street on the crosswalks.

Her home is to the north of the main street, furthermost to the west. The school is to the north of the main street, furthermost to the east. Write a program that helps Cissi to compute the smallest number of streets she needs to cross on her path to school.

Input

The input contains a single line with at most $1\, 000$ letters, each of which is N, S or B. The letters describe the crossing streets exactly in the order Cissi will pass them on her way to school.

Output

A single line with an integer, the smallest number of streets Cissi needs to cross.

Scoring

Your program will be tested on 5 test cases. For each test case you pass, you get 20 points.

For test cases worth 40 points, the number of letters will be at most $20$.

Sample Input 1 Sample Output 1
SNBNNSB
4
Sample Input 2 Sample Output 2
SBSNNBSNNSSSNNNB
8