P9979 [USACO23DEC] Target Practice S

Bessie is a bionic cow. On a number line, she is trying to hit $T$ ($1 \leq T \leq 10^5$) targets at distinct positions. Bessie starts at position $0$ and follows a command sequence of length $C$ ($1 \leq C \leq 10^5$), consisting of `L`, `F`, and `R`: - `L`: Bessie moves one unit to the left. - `R`: Bessie moves one unit to the right. - `F`: Bessie shoots. If there is a target at Bessie's current position, that target is hit and destroyed. It cannot be hit again. If, before Bessie starts, you are allowed to change at most one command in the sequence, what is the maximum number of targets Bessie can hit?

The first line contains $T$ and $C$. The next line contains the positions of the $T$ targets, all distinct integers in the range $[-C,C]$. The next line contains a command sequence of length $C$, containing only the characters `F`, `L`, and `R`.

Output the maximum number of targets Bessie can hit after changing at most one command.

### Sample Explanation 1 If you do not make any changes to the command sequence, Bessie will hit two targets. | Command | Position | Number of Targets Hit | | :----------- | :----------- | :----------- | | Start | 0 | 0 | | L | -1 | 0 | | F | -1 | 1 | | F | -1 | 1 (a target cannot be destroyed 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 three targets: | Command | Position | Number of Targets Hit | | :----------- | :----------- | :----------- | | Start | 0 | 0 | | L | -1 | 0 | | F | -1 | 1 | | F | -1 | 1 (a target cannot be destroyed more than once) | | R | 0 | 1 | | F | 0 | 2 | | R | 1 | 2 | | F | 1 | 3 | ### Sample Explanation 2 If the command sequence is not modified, the only target at position $0$ will be hit. Since a target cannot be destroyed multiple times, the answer is $1$. ### Test Point Properties - Test points $4-6$ satisfy $T,C \le 1000$. - Test points $7-15$ have no additional constraints. Translated by ChatGPT 5