女装大佬

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

题面魔改原因：原题是男选手太多所以要借用女厕所 →_→ 译者表示无法接受

IOI的队服有两种，一种男装，一种是女装。然而很遗憾，所有参赛队伍中并没有女生，只有女装大佬。现在IOI设置了两个发放点，一个点只发放男装，另一个点只发放女装。
现在，所有队伍总共2N个参赛队员，他们排成一列来领取队服，领取队服的规则如下：

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

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

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

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

详情