Gần địa điểm thi của Kỳ thi Olympic Tin học Quốc tế tổ chức tại Nhật Bản có hai nhà vệ sinh. Một nhà vệ sinh chỉ dành cho nữ, còn nhà vệ sinh kia dùng chung cho cả nam và nữ. Nữ có thể sử dụng cả hai nhà vệ sinh, còn nam chỉ có thể sử dụng nhà vệ sinh chung.

Sau khi cuộc thi kết thúc, \(2N\) thí sinh xếp thành một hàng để sử dụng nhà vệ sinh. Mỗi thí sinh trong hàng là nam hoặc nữ. Các thí sinh lần lượt sử dụng nhà vệ sinh theo những quy tắc sau:

• Nếu thí sinh đứng đầu hàng là nữ, người đó vào một nhà vệ sinh đang trống. Nếu cả hai nhà vệ sinh đều trống, người đó vào nhà vệ sinh dành riêng cho nữ.
• Nếu thí sinh đứng đầu hàng là nam, áp dụng các quy tắc sau:
• Nếu nhà vệ sinh chung đang trống, người đứng đầu hàng vào nhà vệ sinh chung.
• Nếu nhà vệ sinh chung không trống nhưng nhà vệ sinh dành riêng cho nữ đang trống, thí sinh nữ đứng gần đầu hàng nhất trong số những người còn đang xếp hàng rời khỏi hàng và vào nhà vệ sinh dành riêng cho nữ.

Mọi thí sinh đều mất \(1\) phút kể từ khi vào đến khi ra khỏi nhà vệ sinh. Có thể bỏ qua thời gian di chuyển đến nhà vệ sinh.

Bạn muốn sắp xếp lại hàng từ trước để đến thời điểm sau \(N\) phút, tất cả các thí sinh đều đã sử dụng xong nhà vệ sinh.

Với một cách sắp xếp lại hàng, mức độ bất mãn của mỗi thí sinh được định nghĩa như sau:

• Mức độ bất mãn của một thí sinh là số người vốn đứng sau người đó trước khi sắp xếp lại, nhưng lại đứng trước người đó sau khi sắp xếp lại.

Định nghĩa này không tính những thay đổi thứ tự xảy ra khi các thí sinh thực sự vào nhà vệ sinh.

Trong số các cách sắp xếp lại hàng để tất cả thí sinh đều sử dụng xong nhà vệ sinh sau \(N\) phút, bạn muốn làm cho mức độ bất mãn lớn nhất của các thí sinh nhỏ nhất có thể.

Yêu cầu

Cho thông tin về \(2N\) thí sinh đang xếp hàng, hãy viết chương trình xác định xem có thể sắp xếp lại hàng để đến thời điểm sau \(N\) phút, tất cả mọi người đều đã sử dụng xong nhà vệ sinh hay không. Nếu có thể, hãy tìm giá trị nhỏ nhất có thể của mức độ bất mãn lớn nhất.

Dữ liệu vào

Đọc dữ liệu từ đầu vào chuẩn theo định dạng sau:

• Dòng đầu tiên chứa số nguyên \(N\), cho biết có \(2N\) thí sinh đang xếp hàng.
• Dòng thứ hai chứa số nguyên \(M\). Giá trị \(M\) và dữ liệu ở \(M\) dòng tiếp theo mô tả các thí sinh trong hàng.
• Trong \(M\) dòng tiếp theo, dòng thứ \(i\) (\(1 \le i \le M\)) chứa xâu \(S_i\) và số nguyên \(K_i\), cách nhau bởi dấu cách.

Từ dữ liệu này, xác định xâu \(X\) có độ dài \(2N\) biểu diễn hàng thí sinh như sau:

• \(X\) được tạo thành bằng cách nối lần lượt các xâu \(X_1, \ldots, X_M\) theo thứ tự đó.
• Xâu \(X_i\) (\(1 \le i \le M\)) được tạo thành bằng cách nối \(K_i\) bản sao của xâu \(S_i\).

Ký tự thứ \(j\) từ trái sang của \(X\) (\(1 \le j \le 2N\)) cho biết giới tính của thí sinh thứ \(j\) tính từ đầu hàng: M là nam và F là nữ.

Dữ liệu ra

In ra đầu ra chuẩn trên một dòng giá trị nhỏ nhất có thể của mức độ bất mãn lớn nhất. Nếu không có cách sắp xếp lại hàng nào để tất cả mọi người đều sử dụng xong nhà vệ sinh sau \(N\) phút, in ra \(-1\).

Ràng buộc

Tất cả dữ liệu vào thỏa mãn các điều kiện sau:

• \(1 \le N \le 1\,000\,000\,000\,000\,000\,000 = 10^{18}\).
• \(1 \le M \le 100\,000\).
• \(1 \le K_i \le 2N \qquad (1 \le i \le M)\).
• \(1 \le |S_i| \le 2N \qquad (1 \le i \le M)\).

Mỗi ký tự của xâu \(S_i\) (\(1 \le i \le M\)) là M hoặc F.

• \(|S_1| + |S_2| + \cdots + |S_M| \le 200\,000\).

Xâu \(X\) được xác định từ dữ liệu vào có độ dài bằng \(2N\). Ở đây, \(|S_i|\) là độ dài của xâu \(S_i\).

Phân nhóm

1. 14 điểm: \(N \le 10\), \(M = 1\) và \(K_1 = 1\).
2. 22 điểm: \(N \le 100\,000\), \(M = 1\) và \(K_1 = 1\).
3. 64 điểm: Không có ràng buộc bổ sung.

Ví dụ

6
1
FFFMMMMMMFFF 1

2

6
1
MMFFMMMMFFMF 1

-1

6
1
MFFFMFMMFFFM 1

0

6
4
M 1
F 2
FM 2
MFFFM 1

0