Петя собрал коллекцию из \(N\) строк, каждая из которых является последовательностью круглых скобок (символы «(» и «)»).
Назовём последовательность скобок сбалансированной, если при просмотре слева направо число открывающих скобок никогда не меньше числа закрывающих, а в конце эти количества равны.
Петя просит у вас помощи. Он хочет составить как можно больше пар из данных строк. Для пары строк \((A, B)\) он берёт их в указанном порядке и склеивает в одну строку \(A + B\). Пара считается хорошей, если полученная строка является сбалансированной. Каждая исходная строка может входить не более чем в одну пару. Требуется определить максимальное количество хороших пар, которое можно составить.
Формат входных данных
В первой строке дано целое число \(N\ (1 \le N \le 50000)\) — количество скобочных последовательностей. В каждой из следующих \(N\) строк записана одна скобочная последовательность, состоящая только из символов «(» и «)». Длина каждой последовательности не превосходит 100.
Формат выходных данных
Выведите одно целое число — максимальное количество пар последовательностей, которые можно выбрать и упорядочить так, чтобы склейка каждой пары давала сбалансированную скобочную последовательность.
| № | Входные данные | Выходные данные |
|
1
|
7
)())
)
((
((
(
)
)
|
2
|
|
2
|
4
(()(
))
(
)))
|
1
|