cho.sh

Alien Ribonucleic Acid

For each strand, compute the largest number of base pairs (B-S and C-F) that can form when disjoint intervals fold onto themselves.

Medium6Dynamic programmingIntervalsNo attempts yetTime limit2sMemory limit512 MB

Problem

An alien species of ribonucleic acid (commonly known as RNA) has been discovered. Short on creativity, the scientists named it alien ribonucleic acid (RNAA). Like the RNA we know, RNAA is a strand made of many bases. The bases are B, C, F, and S, and they bond in pairs. The only possible pairs are B with S and C with F.

While it is active, RNAA folds several intervals of the strand onto itself, forming bonds between its bases. The scientists observed the following:

  • When an interval of the RNAA strand folds, every base in that interval bonds with its matching base.
  • Each base can bond with at most one other base.
  • The folds happen so that the number of bonds formed on the strand is as large as possible.

The figure below shows folds and the bonds they create on strands.

Given the description of an RNAA strand, determine how many bonds form between its bases when the strand becomes active.

Input

The input contains several test cases and ends at end of file (EOF). Each test case is one line with the sequence of bases of an RNAA strand. A strand has at least 1 and at most 300 bases. There are no spaces between the bases of a strand. Each base is one of B, C, F, and S.

Output

For each test case, print one line with the total number of bonds that form when the given strand is activated.