Có hai mỏ than, mỗi mỏ có một nhóm thợ mỏ làm việc. Khai thác than là công việc nặng nhọc, vì vậy các thợ mỏ cần được cung cấp thức ăn để tiếp tục làm việc. Mỗi khi một chuyến hàng thực phẩm đến mỏ, các thợ mỏ sẽ khai thác được một lượng than. Có ba loại chuyến hàng: thịt, cá và bánh mì.

Các thợ mỏ thích chế độ ăn đa dạng và sẽ làm việc hiệu quả hơn nếu thực phẩm được cung cấp phong phú. Cụ thể, mỗi khi nhận được một chuyến hàng mới, họ xét chuyến hàng này cùng hai chuyến hàng trước đó mà mỏ của họ đã nhận được (hoặc ít hơn nếu chưa nhận đủ hai chuyến). Khi đó:

• Nếu tất cả các chuyến hàng được xét đều cùng loại, họ khai thác được \(1\) đơn vị than.
• Nếu có đúng hai loại thực phẩm trong các chuyến hàng được xét, họ khai thác được \(2\) đơn vị than.
• Nếu có cả ba loại thực phẩm, họ khai thác được \(3\) đơn vị than.

Ta biết trước loại thực phẩm của từng chuyến hàng và thứ tự các chuyến hàng sẽ được gửi đi. Bằng cách quyết định chuyến hàng nào được gửi đến mỏ nào, ta có thể ảnh hưởng đến lượng than được khai thác. Không được chia nhỏ một chuyến hàng: toàn bộ chuyến hàng phải được gửi đến một trong hai mỏ.

Hai mỏ không nhất thiết phải nhận cùng số chuyến hàng; thậm chí có thể gửi tất cả các chuyến hàng đến một mỏ.

Cho các loại chuyến hàng theo đúng thứ tự gửi đi, hãy xác định tổng lượng than lớn nhất mà cả hai mỏ có thể khai thác bằng cách lựa chọn mỏ nhận từng chuyến hàng.

Dữ liệu vào

• Dòng thứ nhất chứa số nguyên \(N\), là số chuyến hàng thực phẩm.
• Dòng thứ hai chứa một xâu gồm \(N\) ký tự, mô tả loại thực phẩm của các chuyến hàng theo thứ tự phân phối. Mỗi ký tự là một trong ba chữ cái in hoa: M (thịt), F (cá) hoặc B (bánh mì).

Dữ liệu ra

Ghi một số nguyên duy nhất: tổng lượng than lớn nhất có thể khai thác.

Ràng buộc

• \(1 \le N \le 100\,000\).

Chấm điểm trên hệ thống

Lưu ý: Cách chia nhóm và tính điểm dưới đây là bản điều chỉnh để luyện tập trên hệ thống, không khẳng định tương đương cách chấm tại IOI gốc.

Mỗi nhóm được chấm độc lập: chỉ nhận điểm của nhóm khi vượt qua tất cả bộ kiểm thử trong nhóm; nếu có bộ kiểm thử không đạt thì nhóm nhận 0 điểm. Tổng điểm tối đa là 100.

Nhãn nhóm là phần số trong tên tệp dữ liệu gốc. Tất cả tệp cùng nhãn, kể cả các hậu tố chữ và pf, đều thuộc nhóm đó.

Các ví dụ trong đề không tính điểm.

Ví dụ

6
MBMFFB

12

16
MMBMBBBBMMMMMBMB

29

Nguồn

IOI 2007, ngày thi thứ hai: Miners.