Target Practice

Time limit2sMemory limit1024 MB

Summary

Given targets on a number line and a string of L, R, and F commands, find the most targets Bessie can hit after changing at most one command.

Level: Medium6 of 10
Topics: Simulation, Prefix sum, Array
Solved: No attempts yet

Problem

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 may 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?

Input

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 last line contains the command string of length $C$ , containing only the characters F, L, and R.

Output

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

Examples3

Example 1
Input
```
3 7
0 -1 1
LFFRFRR
```
Expected output
```
3
```
Example 2
Input
```
1 5
0
FFFFF
```
Expected output
```
1
```
Example 3
Input
```
5 6
1 2 3 4 5
FFRFRF
```
Expected output
```
3
```