Shipyard Ballast Kit Maximum Yield

A shipyard stencils an identification code onto every ballast crate before it ships. The code is always the word BALLAST, and the workers spell it out one letter at a time using embossed metal letter tiles pulled from a supply bin. Each completed code consumes exactly one tile of B, two tiles of A, two tiles of L, one tile of S, and one tile of T — no substitutions, and no tile can be reused once it has been used in a code.

The bin's entire current contents are given as a single string listing every uppercase tile currently available, in no particular order; the bin may also contain tiles of letters that never appear in BALLAST, which are simply irrelevant and can be ignored. Given the bin's contents, determine the maximum number of complete BALLAST codes the shipyard can stencil.

Input format

A single line containing a string S of uppercase English letters (A-Z), the current contents of the tile bin. S may be empty.

Output format

Print a single integer: the maximum number of complete BALLAST codes that can be assembled from the tiles in S.

Constraints

• 0 <= length of S <= 200000
• Every character of S is an uppercase letter A-Z.

ABLSTAL

1

BBAAAALLLLSSTT

2