F. ПСП
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Правильная скобочная последовательность (или, коротко, ПСП) — это скобочная последовательность, которую можно превратить в корректное арифметическое выражение, вставив символы «1» и «+» между исходными символами. Например:

  • скобочные последовательности «()()» и «(())» — правильные (из них можно получить выражения «(1)+(1)» и «((1+1)+1)»);
  • скобочные последовательности «)(», «(» и «)» — неправильные.

Обозначим конкатенацию двух строк $$$x$$$ и $$$y$$$ как $$$x+y$$$. Например, «()()» $$$+$$$ «)(» $$$=$$$ «()())(».

У вас есть $$$n$$$ скобочных последовательностей $$$s_1, s_2, \dots, s_n$$$. Вы можете переставить эти строки в любом порядке (можно переставлять только сами строки, но не символы в них).

Ваша задача — переставить строки в таком порядке, чтобы у строки $$$s_1 + s_2 + \dots + s_n$$$ было как можно больше непустых префиксов, являющихся ПСП.

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

В первой строке задано одно целое число $$$n$$$ ($$$1 \le n \le 20$$$).

Далее следуют $$$n$$$ строк, $$$i$$$-я из которых содержит $$$s_i$$$ — скобочную последовательность (строку, состоящую из символов «(» и/или «)». Все последовательности $$$s_i$$$ непустые, их суммарная длина не превосходит $$$4 \cdot 10^5$$$.

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

Выведите одно число — максимальное количество непустых префиксов, являющихся ПСП, у строки $$$s_1 + s_2 + \dots + s_n$$$, если вы переставите строки $$$s_1, s_2, \dots, s_n$$$ оптимальным образом.

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

В первом примере из условия можно склеить строки следующим образом: «(» $$$+$$$ «)» $$$=$$$ «()», у полученной строки будет один префикс, являющийся ПСП: «()».

Во втором примере из условия можно склеить строки следующим образом: «(» $$$+$$$ «)» $$$+$$$ «()()())» $$$+$$$ «(» $$$=$$$ «()()()())(», у полученной строки будет четыре префикса, являющихся ПСП: «()», «()()», «()()()», «()()()()».

В третьем и в четвертом примере всего по одной строке, поэтому поменять порядок строк невозможно.