C. Yuhao и скобки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Однажды Yuhao попалась задача о проверке скобочной последовательности на правильность.

Скобочная последовательность называется правильной скобочной последовательностью, если её можно превратить в корректное математическое выражение, вставив в неё некоторое количество символов «+» и «1». Например, последовательности «(())()», «()» и «(()(()))» являются правильными, а «)(», «(()» и «(()))(» — нет.

Yuhao решил, что эта задача является слишком простой, так что он придумал такую задачу. Вам дано несколько (не обязательно правильных) скобочных последовательностей. Вам нужно соединить некоторые из них в упорядоченные пары так, чтобы каждая скобочная последовательность встречалась не более чем в одной паре, а конкатенация скобочных последовательностей в каждой паре была правильной скобочной последовательностью. Нужно создать как можно больше пар.

Эта задача оказалась слишком сложной для Yuhao. Можете ли вы помочь ему и решить её?

Входные данные

Первая строка содержит одно целое число $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — количество скобочных последовательностей.

Каждая из следующих $$$n$$$ строк содержит одну непустую строку, состоящую из символов «(», «)».

Сумма длин всех скобочных последовательностей не превосходит $$$5 \cdot 10^5$$$.

Обратите внимание, что одна и та же строка может быть перечислена во входных данных несколько раз. В таком случае вы можете использовать каждую из ее копий независимо. Также обратите внимание, что порядок, в котором перечислены строки, не имеет значения.

Выходные данные

Выведите одно целое число — максимальное возможное количество пар, которое можно составить.

Примеры
Входные данные
7
)())
)
((
((
(
)
)
Выходные данные
2
Входные данные
4
(
((
(((
(())
Выходные данные
0
Входные данные
2
(())
()
Выходные данные
1
Примечание

В первом примере, оптимально составить пары «((     )())» и «(     )».