Toilets (Translated)

JOI Spring Training Camp 2015/16
Original Statement / Submission Site

Problem Statement

Near the competition venue of the Japanese Olympiad in Informatics, there are two toilets: one is for women only, and the other is unisex. Women can use either toilet, but men can only use the unisex toilet.

After the competition, 2N participants are standing in a queue to use the toilets. Each participant is either male or female. Participants use the toilets in the following manner:

• If the person at the front of the queue is a woman, she will use any available toilet. If both toilets are available, she chooses the women-only toilet.
• If the person at the front is a man:
  • If the unisex toilet is available, he uses it.
  • If the unisex toilet is occupied and the women-only toilet is free, then the foremost woman in the queue skips ahead to use the women-only toilet.

Each participant takes exactly 1 minute to use the toilet. Time taken to walk to the toilet is ignored.

The goal is to rearrange the initial queue such that all participants finish using the toilet within N minutes.

For any rearrangement of the queue, the dissatisfaction of a participant is defined as the number of people who were originally behind them but are now ahead of them in the rearranged queue. (Note: Changes of order due to toilet usage during execution are not counted towards dissatisfaction.)

We want to minimize the maximum dissatisfaction among all participants, under the condition that all participants finish using the toilet within N minutes.

Task

Given information about the 2N participants in the queue, determine whether it is possible to rearrange them so that all finish using the toilets within N minutes. If it is possible, compute the minimum possible value of the maximum dissatisfaction among the participants.

Input

• The first line contains an integer N.
• The second line contains an integer M.
• The next M lines each contain a string Si and an integer Ki.
  • The full queue is formed by concatenating Ki copies of Si for each line.
  • Each character in Si is either 'M' (male) or 'F' (female).
  • The total length of the final queue is 2N.

Output

Print the minimum possible maximum dissatisfaction value. If no rearrangement can allow all participants to finish within N minutes, print -1.

Constraints

• 1 ≤ N ≤ 1,000,000,000,000,000,000 = 10^18
• 1 ≤ M ≤ 100,000
• 1 ≤ Ki ≤ 2N
• 1 ≤ len(Si) ≤ 2N
• len(S1) + len(S2) + ... + len(SM) ≤ 200,000
• len(S1)×K1 + len(S2)×K2 + ... + len(SM)×KM = 2N

Subtasks

• Subtask 1 [14 points]: N ≤ 10, M = 1, K1 = 1
• Subtask 2 [22 points]: N ≤ 100,000, M = 1, K1 = 1
• Subtask 3 [64 points]: No additional constraints

Sample Input 1

6
1
FFFMMMMMMFFF 1

Sample Output 1

2

Explanation of Output 1

There are 12 participants. We can arrange them like this:

FMMFFMMMMFFF

This arrangement allows all participants to finish within 6 minutes, and the maximum dissatisfaction is 2.

Sample Input 2

6
1
MMFFMMMMFFMF 1

Sample Output 2

-1

No rearrangement can allow everyone to finish within 6 minutes.

Sample Input 3

6
1
MFFFMFMMFFFM 1

Sample Output 3

0

Sample Input 4

6
4
M 1
F 2
FM 2
MFFFM 1

Sample Output 4

0

Note that sample inputs 3 and 4 describe exactly the same queue.