world9969   3년 전

문제

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

경기가 끝났기 때문에, 2N명의 선수들이 화장실을 이용하기 위해 일렬로 섰다. 줄을 선 선수들은 모두 남자나 여자들이다. 선수들은 다음 규칙에 따라 차례로 화장실을 이용한다.

줄의 선두 선수가 여자라면 선두 선수는 빈 화장실에 들어가지만 화장실이 둘 다 비어 있으면 여자 화장실에 들어간다.

줄의 선두 선수가 남자라면 다음 규칙을 따른다.

남녀 화장실이 비어 있으면 선두 선수는 남녀 화장실에 들어간다.

남녀 공용 화장실이 없고 여자 전용 화장실이 비어 있으면 줄을 선 여자들 중 가장 앞에 있는 선수가 줄을 서서 여자 전용 화장실에 들어간다.

모든 선수는 화장실에 들어간 후 나오기까지 1분이 걸린다. 선수가 화장실에 가는 데 걸리는 시간은 무시해도 된다.

줄을 미리 정렬하여 N분 후에 모든 사람들이 화장실 이용을 끝내도록 하고 싶다.

열의 정렬 방식에 대해 선수들의 불만은 다음과 같이 정의된다.

한 선수의 불만은 줄을 세우기 전에는 자신보다 뒤에 있었지만, 정렬을 통해 자신보다 앞으로 나아간 선수들의 수이다.

불만 사항을 정의할 때, 우리는 실제로 화장실에 들어갈 때 발생하는 순서를 바꾸는 것을 고려하지 않는다.

N분 후에 모든 사람들이 화장실 이용을 마친 것처럼 줄을 잘 정렬함으로써 선수들의 불만도를 최대한 줄이기를 바란다.

화장실에 줄을 서 있는 2N 선수에 대한 정보가 주어졌을 때, N분 후에 모든 사람이 화장실 이용을 마친 것처럼 줄을 설 수 있는지를 판단하고, 가능하다면 선수 불만의 최대치로 생각할 수 있는 값 중 가장 작은 값을 찾는 프로그램을 만들어라.

입력

표준 입력에서 아래의 데이터를 읽어라.

첫 번째 줄에는 2N 선수들이 줄을 서 있음을 나타내는 정수 N이 적혀 있다.

두 번째 줄에는 정수 M이 적혀 있다. 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 <= N <= 1_000_000_000_000_000_000 (= 10^18).
1 <= M <= 100_000.
1 <= K_i <= 2N (1 <= i <= M).
1 <= 문자열 Si 길이 <= 2N (1 <= i <= M )
문자열 S_i (1 <= i <= M)의 각 문자는 'M' 또는 'F' 중 하나이다.
(문자열 S1 길이) + (문자열 S2 길이) + · · · + (문자열 SM 길이) <= 200_000.
입력 데이터에서 정해지는 문자열 X의 길이는 2N이다.

댓글을 작성하려면 로그인해야 합니다.