Target Practice

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

요약

로봇이 수직선 위에서 L, R, F 명령 문자열을 따라 움직이며 정해진 위치의 목표물을 맞힌다. 명령을 최대 하나 바꿔 맞힐 수 있는 목표물 수의 최댓값을 구한다. 위치와 목표물 번호에 대한 접두사 동적 계획법으로 푼다.

난이도: 어려움10점 중 8점
유형: 동적 계획법, 누적 합, 배열
정답자: 아직 제출이 없습니다

문제

Bessie is a robovine, also known as a cowborg. She is on a number line trying to shoot a series of $T$ $(1 \leq T \leq 10^5)$ targets located at distinct positions. Bessie starts at position $0$ and follows a string of $C$ $(1 \leq C \leq 10^5)$ commands, each one of L, F, or R:

L: Bessie moves one unit to the left.
R: Bessie moves one unit to the right.
F: Bessie fires. If there is a target at Bessie's current position, it is hit and destroyed, and cannot be hit again.

If you are allowed to change up to one command in the string to a different command before Bessie starts following it, what is the maximum number of targets that Bessie can hit?

입력

The first line contains $T$ and $C$ .

The next line contains the locations of the $T$ targets, distinct integers in the range $\[-C,C]$ .

The next line contains the command string of length $C$ , containing only the characters F, L, and R.

출력

Print the maximum number of targets that Bessie can hit after changing up to one command in the string.

예제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
```