좌파와 우파

면접 대비

시간 제한1초메모리 제한1024 MB

요약

주제 T개와 R 또는 L로 표시된 전문가 N명이 주어질 때, 각 주제에서 한 명 이상을 고르고 우파와 좌파의 수를 같게 맞추는 최소 인터뷰 수를 구하는 문제입니다.

난이도: 보통10점 중 5점
유형: 동적 계획법, 배열
정답자: 아직 제출이 없습니다

문제

선거 시즌이 시작되었다. 당신이 일하는 뉴스 방송국은 다양한 주제에 대해 전문가 의견을 전하려 한다. 공정해 보이도록 국장은 인터뷰하는 전문가들이 정치 성향의 넓은 범위를 고르게 아우르기를 원한다.

정치 성향의 스펙트럼은 매우 다양해서 이를 맞추기가 쉽지 않다. 그래서 검증된 방법을 쓰기로 한다. 각 사람을 우파(rightie) 또는 좌파(leftie) 중 하나로 분류한다. 작업을 가능한 한 빨리 끝내고 싶으므로 인터뷰 횟수를 최소로 하려 한다.

더 정확히 말하면, $T$ 개의 주제와 $N$ 명의 전문가가 있다. 각 전문가는 다뤄야 할 주제 중 정확히 하나와 관련이 있고, 각자 우파 또는 좌파 중 하나이다. 다음 조건을 모두 만족하도록 인터뷰할 전문가 수를 최소로 골라야 한다.

각 주제마다 그 주제의 전문가를 최소 한 명 인터뷰한다.
각 전문가는 최대 한 번만 인터뷰한다. 그렇지 않으면 청중이 지루해한다.
인터뷰한 우파 전문가 수와 좌파 전문가 수가 같다.

입력

첫 줄에 두 정수 $T$ ( $1 \leq T \leq 100$ )와 $N$ ( $1 \leq N \leq 200$ )이 주어진다. 각각 주제 수와 전문가 수이다.

이어서 $N$ 개의 줄이 주어지며, 각 줄에는 정수 $t_i$ ( $1 \leq t_i \leq T$ )와 문자 $c_i$ ( $c_i \in \{R, L\}$ )가 주어진다. $t_i$ 는 $i$ 번째 전문가가 다루는 주제이고, $c_i$ 는 그 전문가가 우파(R)인지 좌파(L)인지를 나타낸다.

출력

조건을 만족하는 최소 인터뷰 횟수 $x$ 를 한 줄에 출력한다. 모든 조건을 만족할 수 없으면 $-1$ 을 출력한다.

예제3

예제 1
입력
```
3 6
1 L
2 R
3 R
2 R
3 L
2 R
```
예상 출력
```
4
```
예제 2
입력
```
3 3
1 L
2 L
3 R
```
예상 출력
```
-1
```
예제 3
입력
```
4 6
1 L
2 L
3 L
1 R
2 R
3 R
```
예상 출력
```
-1
```