Однажды Yuhao попалась задача о проверке скобочной последовательности на правильность.
Скобочная последовательность называется правильной скобочной последовательностью, если её можно превратить в корректное математическое выражение, вставив в неё некоторое количество символов «+» и «1». Например, последовательности «(())()», «()» и «(()(()))» являются правильными, а «)(», «(()» и «(()))(» — нет.
Yuhao решил, что эта задача является слишком простой, так что он придумал такую задачу. Вам дано несколько (не обязательно правильных) скобочных последовательностей. Вам нужно соединить некоторые из них в упорядоченные пары так, чтобы каждая скобочная последовательность встречалась не более чем в одной паре, а конкатенация скобочных последовательностей в каждой паре была правильной скобочной последовательностью. Нужно создать как можно больше пар.
Эта задача оказалась слишком сложной для Yuhao. Можете ли вы помочь ему и решить её?
Выходные данные
Выведите одно целое число — максимальное возможное количество пар, которое можно составить.
Примечание
В первом примере, оптимально составить пары «(( )())» и «( )».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
7
)())
)
((
((
(
)
)
|
2
|
|
2
|
4
(
((
(((
(())
|
0
|
|
3
|
2
(())
()
|
1
|