Near the competition venue of the International Olympiad in Informatics in Japan, there are two toilets. One is a women-only toilet, and the other is a gender-neutral toilet. Women can use either toilet, but men can only use the gender-neutral toilet.

Since the competition has ended, $2N$ contestants have lined up to use the toilets. Each contestant is either male or female. The contestants use the toilets in order, following these rules:

• If the contestant at the front of the line is female, she enters an available toilet. However, if both toilets are available, she enters the women-only toilet.
• If the contestant at the front of the line is male, the following rules apply:
  • If the gender-neutral toilet is available, he enters the gender-neutral toilet.
  • If the gender-neutral toilet is not available but the women-only toilet is available, the female contestant who is closest to the front of the line leaves the line and enters the women-only toilet.

Every contestant takes 1 minute to enter and exit a toilet. The time it takes for a contestant to walk to a toilet can be ignored.

We want to rearrange the line in advance so that everyone finishes using the toilets after $N$ minutes. For a given rearrangement of the line, we define the dissatisfaction of a contestant as follows:

• The dissatisfaction of a contestant is the number of contestants who were behind them before the rearrangement but moved in front of them due to the rearrangement.

In this definition of dissatisfaction, we do not consider the reordering that occurs when contestants actually enter the toilets.

We want to determine a rearrangement of the line such that everyone finishes using the toilets after $N$ minutes, while minimizing the maximum dissatisfaction among all contestants.

Task

Given information about the $2N$ contestants in line, determine if it is possible to rearrange the line such that everyone finishes using the toilets after $N$ minutes. If it is possible, find the minimum possible value for the maximum dissatisfaction of the contestants.

Input

Read the following data from standard input:

• The first line contains an integer $N$, representing that $2N$ contestants are in line.
• The second line contains an integer $M$. The value of $M$ and the following $M$ lines of data represent information about the contestants in line.
• The $i$-th line ($1 \le i \le M$) of the following $M$ lines contains a string $S_i$ and an integer $K_i$, separated by a space.

From this data, define a string $X$ of length $2N$ representing the line of contestants as follows:

• String $X$ is the concatenation of strings $X_1, \dots, X_M$ in this order.
• String $X_i$ ($1 \le i \le M$) is the string formed by concatenating $S_i$, $K_i$ times.

The $j$-th character ($1 \le j \le 2N$) of the string $X$ defined this way represents the gender of the $j$-th contestant from the front of the line. If this character is 'M', the contestant is male; if it is 'F', the contestant is female.

Output

Output the minimum possible value of the maximum dissatisfaction of the contestants on a single line. If it is impossible for everyone to finish using the toilets after $N$ minutes regardless of how the line is rearranged, output -1.

Constraints

All input data satisfies the following conditions:

• $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$ ($1 \le i \le M$).
• $1 \le (\text{length of } S_i) \le 2N$ ($1 \le i \le M$).
• Each character of $S_i$ ($1 \le i \le M$) is either 'M' or 'F'.
• $(\text{length of } S_1) + (\text{length of } S_2) + \dots + (\text{length of } S_M) \le 200\,000$.
• The length of the string $X$ determined by the input data is $2N$.

Subtasks

Subtask 1 [14 points]

• $N \le 10$.
• $M = 1$.
• $K_1 = 1$.

Subtask 2 [22 points]

• $N \le 100\,000$.
• $M = 1$.
• $K_1 = 1$.

Subtask 3 [64 points]

• No additional constraints.

Examples

Input 1

6
1
FFFMMMMMMFFF 1

Output 1

2

Note 1

In Example 1, there are 12 contestants in a line. We rearrange the line as follows: 1. Move the 4th contestant from the front forward by 2 positions. 2. Move the 5th contestant from the front forward by 2 positions.

In this rearrangement, the maximum dissatisfaction is 2. After rearranging, the string representing the line of contestants is FMMFFMMMMFFF ('M' represents male, 'F' represents female). In the rearranged line, let the $i$-th contestant from the front ($1 \le i \le 12$) be contestant $i$. The contestants use the toilets as follows: 1. Contestant 1 and contestant 2 use the toilets. 2. After 1 minute, contestant 3 and contestant 4 use the toilets. 3. After another 1 minute, contestant 5 and contestant 6 use the toilets. 4. After another 1 minute, contestant 7 and contestant 10 use the toilets. 5. After another 1 minute, contestant 8 and contestant 11 use the toilets. 6. After another 1 minute, contestant 9 and contestant 12 use the toilets.

Since there is no rearrangement where the maximum dissatisfaction is less than 2, output 2.

Input 2

6
1
MMFFMMMMFFMF 1

Output 2

-1

Note 2

There is no rearrangement of the line such that everyone finishes using the toilets after 6 minutes.

Input 3

6
1
MFFFMFMMFFFM 1

Output 3

0

Input 4

6
4
M 1
F 2
FM 2
MFFFM 1

Output 4

0

Note 4

In Example 3 and Example 4, the string $X$ determined by the input data is the same: MFFFMFMMFFFM.