Giải bài trực tuyến Học viện Công nghệ Bưu chính Viễn Thông

Bob được ông chủ giao nhiệm vụ làm bảo vệ ở quán bar. Quán bar mới khai trương và mở cửa miễn phí, vì vậy rất đông khách tới. Do đó, mọi người phải xếp hàng lần lượt để vào trong quán bar, và nhiệm vụ của Bob là duy trì trật tự đường lối.

Để duy trì “cân bằng giới tính” trong quán bar, ông chủ mong muốn sự chênh lệch giữa nam và nữ không vượt quá X (X <= 100) trong suốt thời gian hoạt động. Bob cho mọi người xếp hàng và từng người vào một. Nếu như Bob để một người nào đó vào quán bar mà làm mất sự cân bằng giới tính, Bob sẽ bị ông chủ phạt. Vì vậy, Bob luôn đề phòng trước trường hợp này. Nếu như nó có thể xảy ra, Bob sẽ thông báo với mọi người rằng quán bar đã hết chỗ và đóng cửa quán lại, không cho ai vào nữa.

Nếu cứ cứng nhắc như thế này, Bob nhận thấy rằng có thể sẽ phải đóng cửa khá sớm và số lượng người vào trong quán bar khá ít. Vì vậy, anh đã linh hoạt hơn bằng cách cho người đứng thứ 2 trong hàng được phép vào trước, nếu như người đó không làm mất căn bằng giới tính trong quán bar.

Cho biết thứ tự mọi người xếp hàng, các bạn hãy tính xem với cách làm của Bob, số người được vào trong quán bar và uống rượu miễn phí là bao nhiêu?

Input

Dòng đầu tiên là số nguyên X.

Dòng thứ 2 là một xâu s, cho biết giới tính của những người đang xếp hàng. Kí tự ‘M’ thể hiện một người đàn ông, kí tự ‘W’ thể hiện một người phụ nữ trong hàng. Kí tự đầu tiên bên trái thể hiện cho người đứng ở vị trí đầu tiên của hàng.

Output

In ra số lượng người lớn nhất có thể vào trong quán bar.

Example

Test 1:

Input:
1
MWWMWMMWM

Output:

9

Test 2:

Input:
2
WMMMMWWMMMWWMW

Output:

8

Giải thích test 2:

Giải thích test 2:

Tại vị trí người thứ 5, nếu để người này vào, sẽ làm mất cân bằng giới tính, vì vậy người đứng thứ 2 (W) sẽ được vào trước.
Hàng đợi lúc này còn lại MWMMMWWMW, trong quán bar hiện tại có 3 nam và 2 nữ.

Lượt thứ 6 và thứ 7, hai người tiếp vào bình thường, hàng đợi còn lại MMMWWMW, trong quán bar hiện tại có 4 nam và 3 nữ.

Lượt thứ 8, người tiếp (‘M’) vào bình thường, trong quán bar có 5 nam và 3 nữ. Sau lúc này không thể cho ai vào được nữa,
Bob sẽ đóng cửa quán bar lại.