올해 한국정보올림피아드 대회장소에는 화장실이 2개 있다. 한쪽은 여성전용 화장실이고, 다른쪽은 남녀공용 화장실이다. 여성은 어느쪽도 이용할 수 있지만, 남성은 남녀공용 화장실만 이용할 수 있다. 대회 시작 전, 2N명의 선수가 화장실을 이용하기 위해 일렬로 섰다. 선수들은 여성이나 남성중 하나로, 다음 규칙에 따라 순서대로 이용한다.

- 줄의 첫 선수가 여성일 경우에는, 비어있는 화장실을 이용한다. 두 화장실이 모두 비어있는 경우에는 여성전용 화장실에 들어간다.

- 줄의 첫 선수가 남성일 경우, 다음 규칙에 따라 화장실을 이용한다.

남녀 공용 화장실이 비어있을 경우, 줄의 첫 선수가 남녀 공용 화장실에 들어간다.

남녀 공용 화장실이 비어있지 않은 경우, 여성전용 화장실이 비어있다면, 줄에 선 여성 중 가장 앞에 선 선수가 열에서 나와서 여성전용 화장실을 들어간다.

모든 선수가 화장실에 들어가 나오는데까지 1분이 걸린다. 또, 선수가 화장실에 들어가는데 걸리는 시간은 없다고 하자.

열을 미리 정렬해서, N분 후에 모두가 화장실 사용을 마칠 수 있게 하고 싶다. 열의 정렬에 대해, 선수들의 불만족도를 다음과 같이 정의하자.

- 어떤 선수의 불만족도는, 줄에 자신보다 뒤에 서있다가, 정렬 후에 자신의 앞에 오게 된 선수의 수이다.

불만족도의 정의해서, 실제 화장실에 들어갈 때 발생하는 순서의 바뀜은 고려하지 않는다. N분 후의 시점에 모두가 화장실 이용을 끝내도록 잘 정렬하는 중에, 선수의 불만족도의 최댓값을 최소화하고 싶다.

화장실에 서있는 2N명의 선수의 정보가 주어질 때, N분 후에 모두가 화장실 이용을 종료하도록 정렬할 수 있는지를 판단하고, 만약 가능하다면, 선수의 불만족도의 최댓값 중에서, 최솟값을 구하는 프로그램을 작성하여라.

Constraints

모든 입력데이터는 다음의 조건을 만족한다.

• 1 ≤ N ≤ 1 000 000 000 000 000 000 (= 10^18)

• 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이다.

Subtask 1 (14 points)

다음의 조건을 만족한다.

• N ≤ 10

• M = 1

• K1 = 1

Subtask 2 (22 points)

다음의 조건을 만족한다.

• N ≤ 100 000

• M = 1

• K1 = 1

Subtask 3 (64 points)

추가 제한조건이 없다

#5017 upload 30 done 4 how_to_reg 4 call_split Subtask

화장실 timer 1s memory 1024MB

#5017
Subtask

화장실 1s 1024MB