Lefties vs. Righties

Election season has begun. The news network you work for wants to present expert opinions on a variety of important topics. To give the appearance of being unbiased, the news chief insists that the experts interviewed cover a broad range of the political spectrum.

The political spectrum is so varied that this is hard to do. You decide to use a tried and true practice instead: each person is labeled either a rightie or a leftie. You want the job done as quickly as possible, so you want to conduct the fewest interviews possible.

More specifically, there are $T$ topics to be covered and $N$ experts. Each expert is experienced with exactly one of the topics you should cover, and each expert is either a rightie or a leftie. Interview the fewest experts possible such that the following conditions hold.

• For each topic, you interview at least one expert in that topic.
• You interview each expert at most once, since the audience would get bored otherwise.
• The number of rightie experts you interview is the same as the number of leftie experts you interview.

The first line contains two integers $T$ ($1 \leq T \leq 100$) and $N$ ($1 \leq N \leq 200$), the number of topics and the number of experts.

The next $N$ lines each contain an integer $t_i$ ($1 \leq t_i \leq T$) and a character $c_i$ ($c_i \in \{R, L\}$). Here $t_i$ is the topic of the $i$-th expert, and $c_i$ indicates whether that expert is a rightie (R) or a leftie (L).

Output a single integer $x$ on a line by itself, the fewest interviews that can be conducted to satisfy these constraints. If it is not possible to satisfy all constraints, output $-1$.