표적 연습

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

요약

수직선 위의 표적 위치와 L, R, F 명령 문자열이 주어졌을 때, 명령 하나를 바꿔서 맞힐 수 있는 표적의 최대 개수를 구합니다.

난이도: 보통10점 중 6점
유형: 시뮬레이션, 누적 합, 배열
정답자: 아직 제출이 없습니다

문제

Bessie는 로봇 소(robovine)이며 cowborg라고도 부릅니다. 그녀는 수직선 위에서 서로 다른 위치에 놓인 $T$ $(1 \leq T \leq 10^5)$ 개의 표적을 쏘려고 합니다. Bessie는 원점 $0$ 에서 출발하여 길이 $C$ $(1 \leq C \leq 10^5)$ 의 명령 문자열을 차례로 따릅니다. 각 명령은 L, F, R 중 하나입니다.

L: 왼쪽으로 한 칸 이동합니다.
R: 오른쪽으로 한 칸 이동합니다.
F: 사격합니다. 현재 위치에 표적이 있으면 맞혀서 제거하며, 제거된 표적은 다시 맞힐 수 없습니다.

Bessie가 명령을 따르기 전에, 명령 문자열의 명령 하나를 다른 명령으로 최대 한 번 바꿀 수 있습니다. 이때 Bessie가 맞힐 수 있는 표적의 최대 개수는 얼마입니까?

입력

첫 번째 줄에 $T$ 와 $C$ 가 주어집니다.

다음 줄에는 서로 다른 $T$ 개의 표적 위치가 $[-C, C]$ 범위의 정수로 주어집니다.

마지막 줄에는 길이 $C$ 의 명령 문자열이 주어지며, F, L, R 문자로만 이루어져 있습니다.

출력

명령 문자열의 명령을 최대 한 개 바꾼 뒤, Bessie가 맞힐 수 있는 표적의 최대 개수를 출력합니다.

예제3

예제 1
입력
```
3 7
0 -1 1
LFFRFRR
```
예상 출력
```
3
```
예제 2
입력
```
1 5
0
FFFFF
```
예상 출력
```
1
```
예제 3
입력
```
5 6
1 2 3 4 5
FFRFRF
```
예상 출력
```
3
```