Toilets

国際情報オリンピック日本大会の競技会場の近くにはトイレが 2 つある．片方は女性専用トイレで，も う片方は男女共用トイレである．女性はどちらのトイレも利用できるが，男性は男女共用トイレのみ利用 できる．

競技が終了したので，2N 人の選手がトイレを利用するために一列に並んだ．並んだ選手はいずれも男性 または女性のどちらかである．選手は次の規則に従い，順番にトイレを利用する．

• 列の先頭の選手が女性の場合，先頭の選手は空いているトイレに入る．ただしトイレが両方とも空い ている場合は，女性専用トイレに入る．

• 列の先頭の選手が男性の場合は次の規則に従う．

  • 男女共用トイレが空いている場合は，先頭の選手は男女共用トイレに入る．
  • 男女共用トイレが空いておらず，女性専用トイレが空いている場合は，列に並んでいる女性の うちで最も前の選手が列から抜けて女性専用トイレに入る．

すべての選手はトイレに入ってから出るまでに 1 分かかる．選手がトイレに向かうのにかかる時間は無 視してよい．

列をあらかじめ並べ替えることで，N 分後の時点で全員がトイレの利用を終えているようにしたい．

列の並べ替え方に対して，選手の不満度を次のように定義する．

• ある選手の不満度とは，列の並べ替えの前には自分より後ろにいたが，並べ替えによって自分より前 に移った選手の人数である．

不満度の定義において，実際にトイレに入るときに発生する順番の入れ替えは考慮しない．

N 分後の時点で全員がトイレの利用を終えているような列の並べ替えをうまく定めることで，選手の不 満度の最大値をできるだけ小さくしたい．

トイレに並んでいる 2N 人の選手に関する情報が与えられたとき，N 分後の時点で全員がトイレの利用 を終えているように列を並べ替えることができるかを判定し，できる場合は，選手の不満度の最大値とし て考えられる値のうち，最小の値を求めるプログラムを作成せよ．

標準入力から以下のデータを読み込め．

• 1 行目には，整数 N が書かれている．これは，2N 人の選手が列に並んでいることを表す．
• 2 行目には，整数 M が書かれている．M の値と続く M 行のデータは，列に並んでいる選手の情報を 表す．
• 続く M 行のうちの i 行目 (1 ≦ i ≦ M) には，文字列 Si と整数 Ki が空白を区切りとして書かれている．

これらのデータから，選手の列を表現する長さ 2N の文字列 X を次のように定める．

• 文字列 X は，文字列 X1, . . . , XM をこの順に連結することでできる文字列である．
• 文字列 Xi (1 ≦ i ≦ M) は，文字列 Si を Ki 個連結することでできる文字列である． このようにして定めた文字列 X のうち左から j 番目 (1 ≦ j ≦ 2N) の文字は，列の先頭から j 番目の選手 の性別を表す

この文字が ‘M’ のときは男性であることを表し，‘F’ のときは女性であることを表す．

標準出力に，選手の不満度の最大値として考えられる値のうちの，最小の値を 1 行で出力せよ．ただし， どのように列を並べ替えても N 分後に全員がトイレの利用を終えることが不可能な場合は，-1 を出力せよ．

• 1 ≦ N ≦ 1 000 000 000 000 000 000 (= 1018)．
• 1 ≦ M ≦ 100 000．
• 1 ≦ Ki ≦ 2N (1 ≦ i ≦ M)．
• 1 ≦ (文字列 Si の長さ) ≦ 2N (1 ≦ i ≦ M)．
• 文字列 Si (1 ≦ i ≦ M) の各文字は，‘M’ または ‘F’ のいずれかである．
• (文字列 S1 の長さ) + (文字列 S2 の長さ) + · · · + (文字列 SM の長さ) ≦ 200 000．
• 入力データから定まる文字列 X の長さは 2N である．