Background

Original link: https://oier.team/problems/J3B.

Problem Description

Note: All array indices in this statement start from $1$.

There is a lecture with $a$ students and $b$ teachers signed up. The organizer has prepared some seats, and uses a string $s$ to represent the type of each seat. For the $i$-th seat from left to right, $s_i=\texttt{T}$ means it is a teacher seat, and $s_i=\texttt{S}$ means it is a student seat.

Teacher seats can only be used by teachers, student seats can only be used by students, and each seat can be occupied by at most one person.

However, with the current arrangement, not all teachers and students can get a seat. So the organizer plans to make some changes. One modification can choose a teacher seat and change it into a student seat, or choose a student seat and change it into a teacher seat.

Determine the minimum number of modifications needed so that both teachers and students can all have seats. In particular, if no matter how you modify it, it is impossible for everyone to have a seat, output $-1$.

Input Format

The first line contains two positive integers $a,b$, representing the number of students and teachers.

The second line contains a string representing the type of each seat prepared by the organizer.

Output Format

Output one line with one integer, the answer as described in the statement.

3 4
STTSTTTT

1

100 100
SSTT

-1

33 24
SSTTTTSSTSTSTSSTSTSTTTSSSTSSTTSTSSTTTTSTSTTTTSSTTTTTSTTTTSTSSSSS

4

Hint

Sample Explanation #1

There are $3$ students and $4$ teachers signed up. If you change the $2$-nd seat into a student seat, then the students can sit in seats $1,2,4$, and the teachers can sit in any four of seats $3,5,6,7,8$.

Clearly, if you do not adjust the seats, there are not enough seats for students.

Sample Explanation #2

No matter how you modify it, it is obviously impossible for $100$ students and $100$ teachers to sit in only $4$ seats, so output $-1$.

Constraints

This problem has $25$ test points, each worth $4$ points. Let $n$ be the number of characters in the string $s$.

For all testdata, it is guaranteed that $1\le a,b,n\le 10^5$, and the string $s$ contains only uppercase letters S or T.

Translated by ChatGPT 5