기다란 벤치 모양의 식탁에 사람들과 햄버거가 아래 그림과 같이 단위 간격으로 놓여 있다.

사람들은 자신의 위치에서 거리가 \(k\) 이하인 햄버거를 먹을 수 있다. 왼쪽 오른쪽은 상관없다.
위 그림에서 \(k = 1\) 인 경우를 생각해보자.

이 경우에는 모든 사람은 자신의 위치 바로 옆에 인접한 햄버거만 먹을 수 있다.

\(10\)번 위치에 있는 사람은 바로 오른쪽(우리 기준으로) \(11\)번 위치에 있는 햄버거를 먹을 수 있다.

이 경우 다음과 같이 최대 \(5\)명의 사람이 햄버거를 먹을 수 있다.

• \(2\)번 위치에 있는 사람은 \(1\)번 위치에 있는 햄버거를 먹을 수 있다.
• \(4\)번 위치에 있는 사람은 \(5\)번 위치에 있는 햄버거를 먹을 수 있다.
• \(6\)번 위치에 있는 사람은 \(7\)번 위치에 있는 햄버거를 먹을 수 있다.
• \(9\)번 위치에 있는 사람은 \(8\)번 위치에 있는 햄버거를 먹을 수 있다.
• \(10\)번 위치에 있는 사람은 \(11\)번 위치에 있는 햄버거를 먹을 수 있다.
• \(12\)번 위치에 있는 사람은 먹을 수 있는 햄버거가 없다.

만약 \(k = 2\)라고 한다면, 다음과 같이 \(6\)명 모두가 햄버거를 먹을 수 있다.

• \(2\)번 위치에 있는 사람은 \(1\)번 위치에 있는 햄버거를 먹을 수 있다.
• \(4\)번 위치에 있는 사람은 \(3\)번 위치에 있는 햄버거를 먹을 수 있다.
• \(6\)번 위치에 있는 사람은 \(5\)번 위치에 있는 햄버거를 먹을 수 있다.
• \(9\)번 위치에 있는 사람은 \(7\)번 위치에 있는 햄버거를 먹을 수 있다.
• \(10\)번 위치에 있는 사람은 \(8\)번 위치에 있는 햄버거를 먹을 수 있다.
• \(12\)번 위치에 있는 사람은 \(11\)번 위치에 있는 햄버거를 먹을 수 있다.

식탁의 길이 \(N\), 햄버거를 선택할 수 있는 거리 \(k\), 그리고 사람과 햄버거의 위치가 주어졌을 때 햄버거를 먹을 수 있는 사람의 최대 수를 구하는 프로그램을 작성하시오.

20점 상당의 테스트 케이스는 \(N \le 20\)이다.

20점 상당의 테스트 케이스는 \(N \le 2, 000\)이다.

60점 상당의 테스트 케이스는 추가적인 제약 조건이 없다.

입력의 첫 줄에는 두 정수 \(N\)과 \(k\)가 나온다. (\(1≤N≤ 20,000\), \(1≤ k≤ 10\))

그리고 다음 줄에 사람과 햄버거의 위치가 문자 P(사람)와 H(햄버거)로 이루어지는 길이 N인 문자열로 주어진다.

여러분은 첫 줄에 하나의 정수를 출력한다.

이 수는 입력에 대해서 햄버거를 먹을 수 있는 최대 사람 수를 나타낸다.

생성자가 기록되지 않았습니다.

출처 올림피아드 > 한국정보올림피아드 > KOI 2020 > 1차 대회 > 중등부 1번 / 고등부 2번