#2734. 「JOISC 2016 Day 2」女装大佬

内存限制:256 MiB 时间限制:2000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: styx

题目描述

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

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

IOI 的队服有两种,一种男装,一种是女装。然而很遗憾,所有参赛队伍中并没有女生,只有女装大佬。现在 IOI 设置了两个发放点,一个点只发放男装,另一个点只发放女装。

现在,所有队伍总共 2N 个参赛队员,他们排成一列来领取队服,领取队服的规则如下:

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

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

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

输入格式

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

输出格式

一个数,表示重排后最大 Dark 值的最小值,如果在 N 分钟内不能完成领取队服的任务,输出 -1

样例

样例输入 1

6
1
FFFMMMMMMFFF 1

样例输出 1

2

样例解释 1

重排之后排列是这样的:FMMFFMMMMFFF
对于第四和第五个女装大佬,因为有两个男生跑到了他们前面,所以他们的不满度都上升 2
这是最小的方法,因为你找不出更小的方案。

样例输入 2

6
1
MMFFMMMMFFMF 1

样例输出 2

-1

样例输入 3

6
1
MFFFMFMMFFFM 1

样例输出 3

0

样例输入 4

6
4
M 1
F 2
FM 2
MFFFM 1

样例输出 4

0

数据范围与提示

对于全部的数据, 1 \leq N \leq 10^{18} , 1 \leq M \leq 10^5 ,给出的字符串总长小于等于 2\times 10^5

具体子任务限制及得分情况如下表:

Subtask 限制 分数
1 1 \leq N \leq 10 ,且字符串只有一个且只出现一次 14
2 1 \leq N \leq 10^5 ,且字符串只有一个且只出现一次 22
3 无追加限制 64