Instead of writing your ICS4U final exam, your CS teacher Mr. G challenges you to a puzzle! He has laid out a line of $N$ coins numbered from $1$ to $N$ 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 $K$ moves. Can you satisfy his request?

Constraints

For all subtasks:

• $1\le K$
• $K$ will not exceed the number of heads in the initial setup.
• There is at least one coin that is initially heads.

Points Awarded	$N$
2 points	$1\le N\le 10$
4 points	$1\le N\le 20$
9 points	$1\le N\le 400$

Input Specification

The first line contains a string of length $N$. The $i^{\text{th}}$ character of the string denotes the initial state of the $i^{\text{th}}$ coin, with H representing heads and T representing tails.

The second line contains one integer $K$.

Output Specification

Output the maximum score that can be obtained.

Sample Input

THTTHH
3

Sample Output

15

Explanation for Sample Output

The optimal solution is to flip coins $2$, $5$ and $6$ (in that order). This sequence of moves obtains $4+5+6=15$ points.