Bessie là một con bò robot, hay còn gọi là bò cyborg. Cô đang ở trên một trục số và cố gắng bắn một loạt \(T\) mục tiêu (\(1\leq T\leq 10^5\)) nằm tại các vị trí đôi một khác nhau. Bessie bắt đầu tại vị trí \(0\) và thực hiện một xâu gồm \(C\) lệnh (\(1\leq C\leq 10^5\)), mỗi lệnh là L, F hoặc R:

• L: Bessie di chuyển sang trái một đơn vị.
• R: Bessie di chuyển sang phải một đơn vị.
• F: Bessie bắn. Nếu có một mục tiêu tại vị trí hiện tại của Bessie, mục tiêu đó bị bắn trúng và phá hủy, đồng thời không thể bị bắn trúng lần nữa.

Nếu bạn được phép đổi nhiều nhất một lệnh trong xâu thành một lệnh khác trước khi Bessie bắt đầu thực hiện, số mục tiêu lớn nhất Bessie có thể bắn trúng là bao nhiêu?

Dữ liệu vào

Dòng đầu tiên chứa \(T\) và \(C\).

Dòng tiếp theo chứa vị trí của \(T\) mục tiêu, là các số nguyên đôi một khác nhau trong đoạn \([-C,C]\).

Dòng tiếp theo chứa xâu lệnh độ dài \(C\), chỉ gồm các ký tự F, L và R.

Dữ liệu ra

In số mục tiêu lớn nhất Bessie có thể bắn trúng sau khi đổi nhiều nhất một lệnh trong xâu.

Ví dụ

3 7
0 -1 1
LFFRFRR

3

Lệnh    | Vị trí   | Tổng mục tiêu đã bắn trúng
--------+----------+---------------------------
Bắt đầu |  0       | 0
L       | -1       | 0
F       | -1       | 1
F       | -1       | 1 (không thể phá hủy một mục tiêu nhiều lần)
R       |  0       | 1
F       |  0       | 2
R       |  1       | 2
R       |  2       | 2

Lệnh    | Vị trí   | Tổng mục tiêu đã bắn trúng
--------+----------+---------------------------
Bắt đầu |  0       | 0
L       | -1       | 0
F       | -1       | 1
F       | -1       | 1 (không thể phá hủy một mục tiêu nhiều lần)
R       |  0       | 1
F       |  0       | 2
R       |  1       | 2
F       |  1       | 3

1 5
0
FFFFF

1

5 6
1 2 3 4 5
FFRFRF

3

Phân nhóm

• Dữ liệu 4–6: \(T,C\le 1000\).
• Dữ liệu 7–15: Không có ràng buộc bổ sung.

Nguồn

USACO 2023 December Contest, Silver — Target Practice: https://usaco.org/index.php?page=viewproblem2&cpid=1352

Tác giả bài toán: Suhas Nagar