题目描述

题目译自 JOISC 2016 Day2 T3「トイレ」

IOI 的队服有两种，一种男装，一种是女装。然而很遗憾，所有参赛队伍中并没有女生，只有女装大佬。现在 IOI 设置了两个发放点，一个点只发放男装，另一个点只发放女装。

现在，所有队伍总共 $2N$ 个参赛队员，他们排成一列来领取队服，领取队服的规则如下：

1. 当前队首是女装大佬（F），如果领取女装的地方是空的，那么他就会领取女装，否则如果领取男装的地方是空的，他会去领取男装；
2. 当前队首是正常男生（M），如果领取男装的地方是空的，那么他会领取男装，否则如果女装位空着，他就发挥绅♂士精神，给身后的最前面的女装大佬让位，让他先领取女装。

已知任意一个人领取队服都需要一分钟的时间，现在你需要重排所有人的顺序，使他们在 $N$ 分钟内领完队服。

定义一个人的 Dark 值 为：在重排队伍之前在他后面，且重排队伍之后在他前面的人的数量。
你现在需要找出重排后整个队伍最大的 Dark 值至少为多少。

---

输入格式

第一行为一个数 $N$，为领完队服的时限，同时 $2N$ 代表着总领队服人数，需要注意的是，这不意味着正常男生和女装大佬刚好各占 $N$ 个；
第二行为一个数 $M$，指队伍共有 $M$ 种；
之后的 $M$ 行，第 $i$ 行包括一个字符串和一个数字，描述该队伍的组成，其中 M 表示正常男生，F 表示女装大佬，之后的一个数字，表示该字符串连续出现了几次。所有字符串长度乘上出现次数的和等于 $2N$。

---

输出格式

一个数，表示重排后最大 Dark 值的最小值，如果在 $N$ 分钟内不能完成领取队服的任务，输出 -1。

---

样例 1

输入

6
1
FFFMMMMMMFFF 1

输出

2

重排之后排列是这样的：FMMFFMMMMFFF。
对于第四和第五个女装大佬，因为有两个男生跑到了他们前面，所以他们的 Dark 值都上升 $2$。
这是最小的方法，因为你找不出更小的方案。

---

样例 2

输入

6
1
MMFFMMMMFFMF 1

输出

-1

---

样例 3

输入

6
1
MFFFMFMMFFFM 1

输出

0

---

样例 4

输入

6
4
M 1
F 2
FM 2
MFFFM 1

输出

0

---

数据范围与提示

对于全部的数据，$1 \leq N \leq 10^{18}$，$1 \leq M \leq 10^5$，给出的字符串总长小于等于 $2\times 10^5$。

具体子任务限制及得分情况如下表：

Subtask	限制	分数
1	$1 \leq N \leq 10$，且字符串只有一个且只出现一次	14
2	$1 \leq N \leq 10^5$，且字符串只有一个且只出现一次	22
3	无追加限制	64