문제
올해 한국정보올림피아드 대회장소에는 화장실이 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)
추가 제한조건이 없다
입력
첫째 줄에는 정수 N이 쓰여 있다. 이것은, 2N명의 선수가 줄에 서있다는 것을 의미한다.
둘째 줄에는, 정수 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’이면 여성을 의미한다.
출력
선수의 불만도의 최댓값을 최소로한 값을 첫째 줄에 출력하여라. 단, 어떻게 배치해도 N분 후에 전원이 화장실 사용을 마치는 것이 불가능 할 경우, -1을 출력하여라.
예제 #1
6
1
FFFMMMMMMFFF 1
2
예제 #2
6
1
MMFFMMMMFFMF 1
-1
예제 #3
6
1
MFFFMFMMFFFM 1
0
예제 #4
6
4
M 1
F 2
FM 2
MFFFM 1
0
로그인해야 코드를 작성할 수 있어요.