PPC 만들기

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

요약

C와 P로 이루어진 문자열을 최대 K번 교환해 PPC 부분수열의 개수를 가장 많이 만드는 값을 구합니다.

문제

포닉스에게는 아끼던 문자열 $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)$ 의 개수이다.

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

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

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