Instead of writing your ICS4U final exam, your CS teacher Mr. G challenges you to a puzzle! He has laid out a line of coins numbered from to on a table, where each coin is either heads or tails. In one move, you can choose any coin that is currently heads and flip it to become tails. Your score is then increased by the length of the contiguous subsequence of tails created by that move. In order to
pass the course get a good mark, Mr. G asks you to determine the maximum possible score that can be obtained after performing a sequence of moves. Can you satisfy his request?
For all subtasks:
- will not exceed the number of heads in the initial setup.
- There is at least one coin that is initially heads.
The first line contains a string of length . The character of the string denotes the initial state of the coin, with
H representing heads and
T representing tails.
The second line contains one integer .
Output the maximum score that can be obtained.
Explanation for Sample Output
The optimal solution is to flip coins , and (in that order). This sequence of moves obtains points.