题目描述

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

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

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

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

输入格式

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

第一行一个整数N

第二行一个整数M

接下来M行，有一个字符串Si和一个整数Ki构成，中间有空格隔开，字符串中只有'M'（男）和'F'（女）。最后的字符串就是 S1拼接K1次+ S2拼接K2次+ ... +SM拼接KM次

输出格式

输出一个整数，表示答案。如果无论怎么样都没办法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;K1=1

40% N<=100000;M=1;K1=1

100% 1<=N,Ki<=10^18;1<=M<=100000;所有Si字符串长度之和不超过200000