화장실

국제정보올림피아드 일본 대회 경기장 근처에는 화장실이 2개 있다. 한 곳은 여성 전용 화장실이고, 다른 한 곳은 남녀 공용 화장실이다. 여성은 두 화장실 모두 이용할 수 있지만, 남성은 남녀 공용 화장실만 이용할 수 있다.

경기가 끝나서 2N명의 선수가 화장실을 이용하려고 한 줄로 섰다. 줄에 선 선수는 모두 남성 또는 여성이다. 선수들은 다음 규칙에 따라 차례대로 화장실을 이용한다.

• 줄 맨 앞 선수가 여성이면, 빈 화장실에 들어간다. 단, 두 화장실이 모두 비어 있으면 여성 전용 화장실에 들어간다.
• 줄 맨 앞 선수가 남성이면 다음 규칙을 따른다.
  • 남녀 공용 화장실이 비어 있으면, 맨 앞 선수는 남녀 공용 화장실에 들어간다.
  • 남녀 공용 화장실이 비어 있지 않고 여성 전용 화장실이 비어 있으면, 줄에 서 있는 여성 중 가장 앞에 있는 선수가 줄에서 빠져나와 여성 전용 화장실에 들어간다.

선수는 화장실에 들어간 뒤 나올 때까지 1분이 걸린다. 화장실로 이동하는 데 걸리는 시간은 무시한다.

줄을 미리 재배열하여 N분 후에 모든 선수가 화장실 이용을 마치도록 하려고 한다.

재배열 방법마다 선수의 불만도를 다음과 같이 정의한다. 어떤 선수의 불만도는, 재배열 전에는 자기보다 뒤에 있었지만 재배열 후에 자기보다 앞으로 옮겨진 선수의 수이다. 실제로 화장실에 들어갈 때 생기는 순서 변경은 고려하지 않는다.

N분 후에 모든 선수가 화장실 이용을 마치도록 줄을 재배열하면서, 선수의 불만도 최댓값을 가능한 한 작게 하려고 한다.

줄에 서 있는 2N명의 선수에 대한 정보가 주어졌을 때, N분 후에 모든 선수가 화장실 이용을 마치도록 줄을 재배열할 수 있는지 판정한다. 재배열할 수 있다면 불만도 최댓값으로 가능한 값 중 최솟값을 구한다.

표준 입력에서 다음 데이터를 읽는다.

• 첫째 줄에 정수 N이 주어진다. 이는 2N명의 선수가 한 줄로 서 있다는 뜻이다.
• 둘째 줄에 정수 M이 주어진다. 이어지는 M개의 줄은 줄에 선 선수들의 정보를 나타낸다.
• 이어지는 M개 줄 중 i번째 줄(1 ≦ i ≦ M)에는 문자열 S_i와 정수 K_i가 공백으로 구분되어 주어진다.

이 데이터로부터 선수의 줄을 나타내는 길이 2N의 문자열 X를 다음과 같이 정한다.

• 문자열 X는 문자열 X_1, ..., X_M을 이 순서대로 이어 붙인 것이다.
• 문자열 X_i(1 ≦ i ≦ M)는 문자열 S_i를 K_i번 이어 붙인 것이다.

이렇게 정한 X의 왼쪽에서 j번째(1 ≦ j ≦ 2N) 문자는 줄 맨 앞에서부터 j번째 선수의 성별을 나타낸다. 'M'이면 남성, 'F'이면 여성이다.

표준 출력에 선수 불만도 최댓값으로 가능한 값 중 최솟값을 한 줄에 출력한다. 어떻게 줄을 재배열해도 N분 후에 모두 화장실 이용을 마칠 수 없으면 -1을 출력한다.

• $1 \le N \le 10^{18}$
• $1 \le M \le 100000$
• $1 \le K_i \le 2N$ ($1 \le i \le M$)
• $1 \le |S_i| \le 2N$ ($1 \le i \le M$)
• 문자열 S_i의 각 문자는 'M' 또는 'F'이다 ($1 \le i \le M$).
• $|S_1| + |S_2| + \cdots + |S_M| \le 200000$
• 입력으로 정해지는 문자열 X의 길이는 2N이다.