Toilets

Time limit1sMemory limit512 MB

Summary

Given a line of 2N men and women (in run-length form), rearrange it so everyone finishes within N minutes and minimize the largest discontent, or report -1.

Level: Hard9 of 10
Topics: Binary search, Greedy, Math
Solved: No attempts yet

Problem

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

The competition has ended, and 2N contestants line up to use the toilets. Each contestant is either male or female. They use the toilets one at a time under the following rules.

If the contestant at the front of the line is female, she enters an empty toilet. If both toilets are empty, she enters the women-only toilet.
If the contestant at the front of the line is male, the following rules apply.
- If the unisex toilet is empty, he enters the unisex toilet.
- If the unisex toilet is occupied and the women-only toilet is empty, the frontmost woman in the line leaves the line and enters the women-only toilet.

Each contestant takes 1 minute from entering a toilet until leaving it. Time spent walking to a toilet is ignored.

By rearranging the line in advance, we want everyone to have finished using the toilets after N minutes.

For a given rearrangement, the discontent of a contestant is the number of contestants who were behind that contestant before the rearrangement and are in front of that contestant after it. Reordering that happens when contestants actually enter the toilets is not counted.

By choosing a rearrangement in which everyone finishes after N minutes, we want to make the maximum discontent over all contestants as small as possible.

Given information about the 2N contestants in line, determine whether the line can be rearranged so that everyone finishes after N minutes. If it can, find the smallest possible value of the maximum discontent.

Input

Read the following data from standard input.

The first line contains an integer N. The line has 2N contestants.
The second line contains an integer M. The M lines that follow describe the contestants in line.
The i-th of those M lines (1 ≦ i ≦ M) contains a string S_i and an integer K_i, separated by a space.

From this data, define a string X of length 2N as follows.

X is the concatenation of the strings X_1, ..., X_M in this order.
X_i (1 ≦ i ≦ M) is the concatenation of K_i copies of S_i.

The j-th character of X (1 ≦ j ≦ 2N), counted from the front of the line, gives the gender of the j-th contestant. 'M' means male, and 'F' means female.

Output

Print, on one line, the smallest possible value of the maximum discontent. If no rearrangement lets everyone finish after N minutes, print -1.

Constraints

$1 \le N \le 10^{18}$
$1 \le M \le 100000$
$1 \le K_i \le 2N$ ( $1 \le i \le M$ )
$1 \le |S_i| \le 2N$ ( $1 \le i \le M$ )
Each character of S_i is 'M' or 'F' ( $1 \le i \le M$ ).
$|S_1| + |S_2| + \cdots + |S_M| \le 200000$
The length of X determined by the input is 2N.

Examples4

Example 1
Input
```
6
1
FFFMMMMMMFFF 1
```
Expected output
```
2
```
Example 2
Input
```
6
1
MMFFMMMMFFMF 1
```
Expected output
```
-1
```
Example 3
Input
```
6
1
MFFFMFMMFFFM 1
```
Expected output
```
0
```
Example 4
Input
```
6
4
M 1
F 2
FM 2
MFFFM 1
```
Expected output
```
0
```