시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB153625546.218%

문제

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.

예제 입력 1

3 7
0 -1 1
LFFRFRR

예제 출력 1

3

If you make no changes to the string, Bessie will hit two targets:

Command | Position | Total Targets Hit
--------+----------+-------------------
Start   |  0       | 0 
L       | -1       | 0
F       | -1       | 1
F       | -1       | 1 (can't destroy target more than once)
R       |  0       | 1
F       |  0       | 2
R       |  1       | 2
R       |  2       | 2

If you change the last command from R to F, Bessie will hit all three targets:

Command | Position | Total Targets Hit
--------+----------+-------------------
Start   |  0       | 0 
L       | -1       | 0
F       | -1       | 1
F       | -1       | 1 (can't destroy target more than once)
R       |  0       | 1
F       |  0       | 2
R       |  1       | 2
F       |  1       | 3

예제 입력 2

1 5
0
FFFFF

예제 출력 2

1

If the commands are left unchanged, the only target at 0 will be destroyed. Since a target cannot be destroyed multiple times, the answer is 1.

예제 입력 3

5 6
1 2 3 4 5
FFRFRF

예제 출력 3

3