PPC 만들기

시간 제한1초메모리 제한1024 MB

요약

P와 C로 이루어진 문자열에서 두 위치를 바꾸는 연산을 최대 K번 해서, 앞 두 문자가 P이고 세 번째가 C인 삼중항의 개수를 최대로 만든다.

문제

포닉스에게는 아끼던 문자열 $S$ 가 있다. $S$ 는 길이가 $N$ 이며 알파벳 대문자 C와 P만으로 이루어져 있는 문자열이다. 문자열 $S$ 의 $i$ 번째 문자는 $S\_i$ 와 같이 나타낸다.

포닉스는 PPC에 참가하는 팀들을 위해 문자열 $S$ 로 대회장을 장식하려 한다. 포닉스는 대회 전, $S$ 에 다음과 같은 연산을 최대 $K$ 번 시행할 수 있다.

포닉스의 목표는 완성된 문자열 $S$ 에 PPC 부분문자열이 가장 많게 하는 것이다. PPC 부분문자열의 개수란, $1 \le i\<j\<k \le N$ 이고 $S\_i=S\_j=$ P, $S\_k=$ C인 $(i,j,k)$ 의 개수를 의미한다.

포닉스가 만들 수 있는 PPC 부분문자열의 개수의 최댓값을 구하여라.

첫 번째 줄에 문자열 $S$ 의 길이 $N$ 과 연산의 최대 사용 횟수 $K$ 가 공백으로 구분되어 주어진다. ( $1\le K\le N\le 200\\,000$ )

두 번째 줄에 길이가 $N$ 인 문자열 $S$ 가 주어진다. $S$ 는 알파벳 대문자 C와 P만으로 이루어져 있음이 보장된다.

포닉스가 만들 수 있는 PPC 부분문자열의 개수의 최댓값을 출력한다.