AT_joisc2016_f.トイレ

JOI会场附近有两个厕所，一个是女性专用的，另外一个是男女混用的。女性可以用两种厕所，但是男性只能用男女混用的。
比赛结束后，有$2N$个选手排成一列上厕所。排队的人有男的和女的。他们将按照下列规则排队上厕所。

• 如果当前是一个女生在队头，那么选择空的那个厕所进入。若两边都是空的，优先进入女性专用厕所。

• 如果当前是一个男生在队头，他会遵守以下规则。

  • 如果男女公用厕所是空的，他就会去男女共用的厕所。

  • 如果男女公用厕所不是空的但是女性专用厕所是空的，他会请队伍里面最前面的一个女生去女性专用厕所。

所有的选手都会用1分钟上厕所。你可以忽略选手出入厕所的时间。
但是这样可能不会在$N$分钟之内上完厕所，于是我们希望能够改变选手排队的次序，进而保证所有选手能在$N$分钟之内上完厕所。
排完次序之后，我们定义一个选手的不满度。

• 一个选手的不满度定义为排序之前在这个选手的后面但是排序后在该选手的前面的人数。

不满度与排队时进入厕所次序无关。

我们希望能够适当地排序后使得所有人能在$N$分钟之内上完厕所，并且不满度最小。

我们给定$2N$个选手的初始排队顺序，确定是否能够在$N$分钟内上完厕所。如果可以的话，写出一个程序，找到选手的不满度的最小值。

• 第一行，输入一个$N$。表示有$2N$个人排序。

• 第二行，输入一个$M$。

• 接下来$M$行，有一个字符串$S_i$和整数$K_i$，并且以空格符间隔。这些数据表示用$K_i$个$S_i$依次接在后面。

我们以此定义出一个字符串$X$（即为上述初始排队队列）。$X$左起第$j(j \leq 2N)$个字符代表这个选手的性别。若这个字符是M，代表这个选手是男性，若这个字符是F，那么这个选手是女性。

输出选手最小的可能不满度值。但是如果无论如何排序都无法在$N$分钟以内上完厕所，输出-1

输入数据满足以下数据。

• $1 \leq N \leq 10^{18}$。

• $1 \leq M \leq 100000$。

• $1 \leq K_i \leq 2N (1 \leq i \leq M)$。

• $1 \leq |S_i| \leq 2N (1 \leq i \leq M)$，其中$|S_i|$代表$S_i$的长度。

• $S_i (1 \leq i \leq M)$的所有字符都是M或者F。

• 通过$K_i$和$S_i$构造的字符串$X$，满足$X$长度为$2N$。

任务

子任务1[14分]

满足以下条件。

• $N \leq 10$。

• $M=1$。

• $K_i=1$。

子任务2[22分]

满足以下条件。

• $N \leq 100000$。

• $M=1$。

• $K_i=1$。

子任务3[64分]

没有追加条件。

测试样例

输入1

6
1
FFFMMMMMMFFF 1

输出1

2

重排序列之后为FMMFFMMMMFFF。

输入2

6
1
MMFFMMMMFFMF 1

输出2

-1

无论如何排序都无法完成在$N$分钟之内完成。

输入3

6
1
MFFFMFMMFFFM 1

输出3

0

输出4

6
4
M 1
F 2
FM 2
MFFFM 1

输出4

0

输入样例3和4构造的字符串$X$是一样的，重排序列之后为MFFFMFMMFFFM。