KTH Challenge 2016 Open

Start

2016-06-12 10:00 CEST

KTH Challenge 2016 Open

End

2016-06-12 14:00 CEST
The end is near!
Contest is over.
Not yet started.
Contest is starting in -496 days 2:33:31

Time elapsed

4:00:00

Time remaining

0:00:00

Problem F
Hay Bales

/problems/haybales/file/statement/en/img-0001.jpg
Picture by stanze

Peter has lined up hay bales. Some hay bales contain parasites and he wants to move the infected hay bales to the back of the sequence, to minimize the chance that the parasites spread. To sort the haybales, he repeatedly takes out any three consecutive hay bales and puts them back in sorted order. Your task is to calculate the minimum number of operations Peter has to execute to sort the sequence.

Input

The input contains a single string $s$ ($3 \leq |s| \leq 500$), the sequence of hay bales. Each character of $s$ is either ‘C’ (for a clean hay bale) or ‘P’ (for an infected one).

Output

The output must contain one integer, the minimum number of steps Peter has to execute.

Sample Input 1 Sample Output 1
CPCC
1
Sample Input 2 Sample Output 2
PPPPCCCC
8
Sample Input 3 Sample Output 3
CCCCPPPP
0