Making PPC

Time limit1sMemory limit1024 MB

Summary

Given a string of C and P characters and at most K swaps, maximize the number of PPC subsequences (P, then P, then C, in order).

Level: Medium5 of 10
Topics: Greedy, Two pointers, String
Solved: No attempts yet

Problem

Phoenix has a string $S$ that he treasures. $S$ has length $N$ and consists only of the uppercase letters C and P. The $i$ -th character of $S$ is written $S_i$ .

Phoenix wants to decorate the venue of a contest with $S$ for the teams taking part in PPC. Before the contest, Phoenix can perform the following operation on $S$ at most $K$ times.

Choose two integers $i$ and $j$ with $1 \le i < j \le N$ , and swap $S_i$ and $S_j$ .

Phoenix's goal is to make the finished string $S$ contain as many PPC subsequences as possible. A PPC subsequence is a triple $(i, j, k)$ with $1 \le i < j < k \le N$ , $S_i = S_j =$ P, and $S_k =$ C.

Input

The first line contains the length $N$ of the string $S$ and the maximum number of operations $K$ , separated by a space. ( $1 \le K \le N \le 200000$ )

The second line contains the string $S$ of length $N$ . It is guaranteed that $S$ consists only of the uppercase letters C and P.

Output

Print the maximum number of PPC subsequences that Phoenix can make.

Examples3

Example 1
Input
```
3 1
CPP
```
Expected output
```
1
```
Example 2
Input
```
8 2
CCPCPPCP
```
Expected output
```
21
```
Example 3
Input
```
3 1
CPC
```
Expected output
```
0
```