Hay Bales

Interview

Time limit2sMemory limit512 MB

Summary

Given a string of C and P, each move sorts any three consecutive characters so all C come before all P; find the minimum number of moves to fully sort the whole row.

Level: Medium6 of 10
Topics: Greedy, String, Simulation, Dynamic programming
Solved: No attempts yet

Problem

Peter has lined up his hay bales in a row. Some of the bales carry parasites. To keep the parasites from spreading, Peter wants every infected bale at the back of the row.

In one operation Peter picks any three consecutive bales, takes them out, and puts them back in sorted order: the clean bales first, then the infected ones. The row is sorted once every clean bale stands in front of every infected bale.

Compute the minimum number of operations Peter has to execute to sort the row.

Input

The first line contains a string $s$ ( $3 \le |s| \le 500$ ), the sequence of hay bales. Each character of $s$ is either C for a clean bale or P for an infected one. The characters are given in the order the bales stand in the row.

Output

Print one integer, the minimum number of operations Peter has to execute.

Examples3

Example 1
Input
```
CPCC
```
Expected output
```
1
```
Example 2
Input
```
PPPPCCCC
```
Expected output
```
8
```
Example 3
Input
```
CCCCPPPP
```
Expected output
```
0
```