题目描述

竞赛比完之后，水箱里充满水的选手们鱼贯而出。凡华中学的厕所规划的很糟，只有两个厕位，于是厕所门前排起了长长的队伍。

厕所有两个，一个是女生专用厕所，另一个是男女混用厕所。一共有 $2N$ 个选手正在排队，男女生数量可能不同。如果队头的是妹子，只要某个厕所是空的就可以进入，但是如果两个厕所都是空的，那么优先进入女性专用厕所。而如果队头是个绅♂士，只有在男女混用厕所是空的时候才能使用；如果只有女性专用厕所是空的，那么队伍中最靠前的妹子就可以不用继续等直接如厕。我们假设所有人如厕都需要花 $1$ 分钟，不考虑切换的时间。

然而，$N$ 分钟后，就要开饭了，所有人必须如厕完，不过看样子似乎来不及。主办方可以重新调换顺序，不过有些人会因为新的顺序中自己更加后面了而感到不满，不满度是自己相比于原队列后退了几个顺序（除此之外跟自己的实际如厕顺序无关）。

主办方发现了这一点，所以希望你帮助他们解决这个问题，设计出一种方案，对于其中不满意度最大的学生，尽可能让他的不满意度最小。你只需要告诉他们最不满意的学生的不满意度是多少。

输入格式

由于人相当多，我们用几段字符串来描述这个队列。

第一行一个整数 $N$ ；

第二行一个整数 $M$ ；

接下来 $M$ 行，由一个字符串 $S_i$ 和一个整数 $K_i$ 构成，中间有空格隔开，字符串中只有M（男）和F（女）。最后的字符串就是 $S_1$ 拼接 $K_1$次 + $S_2$ 拼接 $K_2$ 次+ ... + $S_M$ 拼接 $K_M$ 次。

输出格式

输出一个整数，表示答案。如果无论怎么样都没办法在 $N$ 分钟之内达成，请输出 -1 。

5
3
FFF 1
M 5
FF 1

2

提示

原队列是 FFFMMMMMFF ，

改进后的队列是 FMMFFMMMFF ，

所以厕所会按照下面的时间使用：

分钟 1   2   3   4   5
共用 2   3   6   7   8
女用 1   4   5   9   10

两个妹子往后面移动了 $2$ 位，所以不满意度是 $2$ 。

对于 $20 \%$ 的数据，$N \le 10,M=1,K_1=1$ ；

对于 $40 \%$ 的数据， $N\le100000,M=1,K_1=1$；

对于 $100 \%$ 的数据， $1\le N,K_i\le10^{18},1\le M\le100000, \sum |S_i| \le 200000$。