가위바위보 기계

가위바위보 기계는 바위, 보, 가위 중 하나를 무작위로 낸다. 나에게도 똑같이 동작하는 작은 기계가 있다. 대결을 시작하기 전에 상대 기계는 자기가 낼 것을 길이 $n$짜리 목록으로 미리 만들어 두고, 내 기계도 길이 $m$짜리 목록을 미리 만들어 둔다. 나는 두 목록을 모두 알고 있다. 각 항목은 바위, 보, 가위 중 하나이고, R은 바위, P는 보, S는 가위를 뜻한다.

대결은 두 목록을 앞에서부터 한 항목씩 맞대어 치른다. 시작하기 전에 상대 목록의 앞쪽을 원하는 만큼 건너뛸 수 있다. 건너뛰고 남은 첫 항목이 내 목록의 첫 항목과 붙는다. 한 번 시작하면 더 건너뛸 수 없고, 두 목록 중 하나가 떨어질 때까지 한 판씩 이어서 치른다. 내 목록이 남아 있어도 상대 목록이 먼저 떨어지면 대결은 거기서 끝난다. 비긴 판은 세지 않는다.

예를 들어 상대 목록이 RSPPSSSRRPPR이고 내 목록이 RRRR이면, 앞에서 세 항목이나 네 항목을 건너뛰고 시작할 때 세 판을 이겨서 가장 많이 이긴다.

그림 1. $n = 12$, $m = 4$일 때 가장 많이 이기는 시작 위치.

두 목록이 주어지면 내 기계가 이기는 판 수의 최댓값을 구하라.

첫째 줄에 두 정수 $n$과 $m$이 주어진다 ($1 \le m < n \le 100000$). $n$은 상대 기계 목록의 길이, $m$은 내 기계 목록의 길이다. 둘째 줄에 상대 기계의 목록, 셋째 줄에 내 기계의 목록이 R, P, S로만 이루어진 문자열로 주어진다.

첫째 줄에 내 기계가 이기는 판 수의 최댓값을 출력한다.