国际信息奥林匹克日本大会的比赛场地附近有两个厕所。一个是女性专用厕所，另一个是男女共用厕所。女性可以使用任何一个厕所，而男性只能使用男女共用厕所。

比赛结束后，$2N$ 名选手排成一列准备使用厕所。每位选手要么是男性，要么是女性。选手们按照以下规则依次使用厕所：

• 如果队首的选手是女性，该选手进入一个空闲的厕所。如果两个厕所都空闲，则进入女性专用厕所。
• 如果队首的选手是男性，则遵循以下规则：
  • 如果男女共用厕所空闲，该选手进入男女共用厕所。
  • 如果男女共用厕所不空闲，但女性专用厕所空闲，则队列中排在最前面的女性选手离开队列，进入女性专用厕所。

所有选手从进入厕所到离开需要 1 分钟。选手前往厕所所需的时间可以忽略不计。

我们希望通过预先重新排列队列，使得在 $N$ 分钟后所有选手都已使用完厕所。对于一种队列的排列方式，定义选手的“不满度”如下：

• 某位选手的不满度是指，在重新排列之前排在自己后面，但通过重新排列后移到了自己前面的选手的数量。

在不满度的定义中，不考虑实际进入厕所时发生的顺序交换。

通过合理确定在 $N$ 分钟后所有选手都能使用完厕所的队列排列方式，使得选手不满度的最大值尽可能小。

题目描述

给定有关排队等待厕所的 $2N$ 名选手的信息，判断是否可以重新排列队列，使得在 $N$ 分钟后所有选手都已使用完厕所。如果可以，求出选手不满度最大值可能的最小值。

输入格式

从标准输入读取以下数据：

• 第 1 行包含一个整数 $N$，表示有 $2N$ 名选手排成一列。
• 第 2 行包含一个整数 $M$。$M$ 的值以及随后的 $M$ 行数据表示排队选手的相关信息。
• 随后的 $M$ 行中的第 $i$ 行 ($1 \le i \le M$) 包含一个字符串 $S_i$ 和一个整数 $K_i$，中间以空格分隔。

根据这些数据，定义表示选手队列的长度为 $2N$ 的字符串 $X$ 如下：

• 字符串 $X$ 是将字符串 $X_1, \dots, X_M$ 按此顺序连接而成的字符串。
• 字符串 $X_i$ ($1 \le i \le M$) 是将字符串 $S_i$ 重复连接 $K_i$ 次而成的字符串。

如此确定的字符串 $X$ 中，从左起第 $j$ 个字符 ($1 \le j \le 2N$) 表示队列中从前往后第 $j$ 位选手的性别。字符为 'M' 时表示男性，为 'F' 时表示女性。

输出格式

在标准输出中，输出选手不满度最大值可能的最小值。如果无论如何重新排列队列，都无法在 $N$ 分钟后让所有选手使用完厕所，则输出 -1。

数据范围

所有输入数据满足以下条件：

• $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{字符串 } S_i \text{ 的长度}) \le 2N$ ($1 \le i \le M$)。
• 字符串 $S_i$ ($1 \le i \le M$) 的每个字符均为 'M' 或 'F'。
• $(\text{字符串 } S_1 \text{ 的长度}) + (\text{字符串 } S_2 \text{ 的长度}) + \dots + (\text{字符串 } S_M \text{ 的长度}) \le 200\,000$。
• 由输入数据确定的字符串 $X$ 的长度为 $2N$。

子任务

子任务 1 [14 点]

满足以下条件： $N \le 10$。 $M = 1$。 * $K_1 = 1$。

子任务 2 [22 点]

满足以下条件： $N \le 100\,000$。 $M = 1$。 * $K_1 = 1$。

子任务 3 [64 点]

无额外限制。

样例

样例输入 1

6
1
FFFMMMMMMFFF 1

样例输出 1

2

说明 1

样例 1 中有 12 名选手排成一列。按如下方式重新排列队列：

1. 将从前往后第 4 位的选手向前移动 2 个位置。
2. 将从前往后第 5 位的选手向前移动 2 个位置。

在这种排列方式下，选手不满度的最大值为 2。重新排列后，表示选手队列的字符串变为 FMMFFMMMMFFF（'M' 表示男性，'F' 表示女性）。在重新排列后的队列中，将从前往后第 $i$ 位 ($1 \le i \le 12$) 的选手称为选手 $i$。选手们按如下方式使用厕所：

1. 选手 1 和选手 2 使用厕所。
2. 1 分钟后，选手 3 和选手 4 使用厕所。
3. 再过 1 分钟，选手 5 和选手 6 使用厕所。
4. 再过 1 分钟，选手 7 和选手 10 使用厕所。
5. 再过 1 分钟，选手 8 和选手 11 使用厕所。
6. 再过 1 分钟，选手 9 和选手 12 使用厕所。

由于不存在不满度最大值小于 2 的排列方式，故输出 2。

样例输入 2

6
1
MMFFMMMMFFMF 1

样例输出 2

-1

说明 2

不存在能在 6 分钟后让所有选手使用完厕所的队列排列方式。

样例输入 3

6
1
MFFFMFMMFFFM 1

样例输出 3

0

样例输入 4

6
4
M 1
F 2
FM 2
MFFFM 1

样例输出 4

0

样例 3 和样例 4 中，由输入数据确定的字符串 $X$ 相同，均为 MFFFMFMMFFFM。