Тим проходит тест, состоящий из \(4n\) вопросов; каждый вопрос имеет \(4\) варианта ответа: 'A', 'B', 'C' и 'D'. Для каждого варианта ответа существует ровно \(n\) правильных ответов, соответствующих этому варианту — это означает, что есть \(n\) вопросов с ответом 'A', \(n\) вопросов с ответом 'B', \(n\) вопросов с ответом 'C' и \(n\) вопросов с ответом 'D'.
Для каждого вопроса Тим записал свой ответ на бланке ответов. Если он не мог определить ответ, он оставлял знак вопроса '?' для этого вопроса.
Вам дан бланк ответов из \(4n\) символов. Какое максимальное количество правильных ответов может получить Тим?
Выходные данные
Для каждого набора входных данных выведите одно целое число — максимальный балл, который Тим может получить.
Примечание
В первом наборе входных данных есть ровно один вопрос с каждым ответом 'A', 'B', 'C' и 'D'; поэтому возможно, что Тим получит все свои ответы правильными.
Во втором наборе входных данных есть только два правильных ответа 'A', что делает его результатом ровно \(2\) балла в любом случае.
В третьем наборе входных данных Тим может получить максимум \(2\) правильных ответа с вариантом 'A' и \(2\) правильных ответа с вариантом 'B'. Например, он получил бы \(4\) балла, если бы правильными ответами были 'AACCBBDD'.
В четвертом наборе входных данных он отказывается отвечать на любые вопросы, поэтому его результат в любом случае равен \(0\) баллов.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
6
1
ABCD
2
AAAAAAAA
2
AAAABBBB
2
????????
3
ABCABCABCABC
5
ACADC??ACAC?DCAABC?C
|
4
2
4
0
9
13
|