oql believes that a string of length 4 is "excellent" if and only if its 1st, 2nd, and 4th characters are the same, and its 3rd character is different from these three characters.

Therefore, ccpc is an excellent string. Similarly, ppcp is also excellent.

One day, oql received a string $S$ consisting only of c and p from Iris. oql calculated the total number of excellent subsequences of length 4 in this string, but felt it was too small. So, he asked Iris to modify the string. Each modification costs 1 cat treat and consists of swapping a pair of adjacent different characters.

Given that oql has a total of $m$ cat treats, he wants to know the maximum possible number of excellent subsequences of length 4 in the resulting string after spending exactly $m$ cat treats.

Input

The first line contains a string $S$ consisting only of c and p ($1 \le |S| \le 500$). The second line contains a non-negative integer $m$ ($0 \le m \le 500$), representing the number of cat treats oql has.

Output

Output a single integer representing the maximum possible number of excellent subsequences of length 4 in the resulting string after spending exactly $m$ cat treats.

Examples

Input 1

cpcc
1

Output 1

1

Input 2

cppcccpc
3

Output 2

16