4329. 省选之后

【题目背景】

而你的教练：

补充：T1不会可以埋了。----黄笑凡

现在是3.1······吗？不对，现在是3.7的中午，刚刚参加完省选day1的你觉得自己炸完了，不仅是你的分数要炸了，更重要的是，你的膀胱也要炸了！

【题目描述】

考场厕所设计的很糟糕，只有两个厕所，一个是女生专用厕所，另一个是男女混用厕所。一共有$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≤10,M=1,K_1=1$；

对于$40$%的数据，$N≤10^3,M=1,K_1=1$；

对于$60$%的数据，$N≤10^5,M=1,K_1=1$；

对于$20$%的数据，男生的数量大于女生的数量；

对于$100$%的数据，$1≤N,K_i≤10^{18},1≤M≤10^5,∑∣S_i∣≤2×10^5$。

数据保证答案不超过$long long$

大样例