#P3615. 如厕计划

如厕计划

题目描述

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

厕所有两个,一个是女生专用厕所,另一个是男女混用厕所。一共有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