Правильная скобочная последовательность (или, коротко, ПСП) — это скобочная последовательность, которую можно превратить в корректное арифметическое выражение, вставив символы «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\) было как можно больше непустых префиксов, являющихся ПСП.
Выходные данные
Выведите одно число — максимальное количество непустых префиксов, являющихся ПСП, у строки \(s_1 + s_2 + \dots + s_n\), если вы переставите строки \(s_1, s_2, \dots, s_n\) оптимальным образом.
Примечание
В первом примере из условия можно склеить строки следующим образом: «(» \(+\) «)» \(=\) «()», у полученной строки будет один префикс, являющийся ПСП: «()».
Во втором примере из условия можно склеить строки следующим образом: «(» \(+\) «)» \(+\) «()()())» \(+\) «(» \(=\) «()()()())(», у полученной строки будет четыре префикса, являющихся ПСП: «()», «()()», «()()()», «()()()()».
В третьем и в четвертом примере всего по одной строке, поэтому поменять порядок строк невозможно.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
(
)
|
1
|
|
2
|
4
()()())
(
(
)
|
4
|
|
3
|
1
(())
|
1
|
|
4
|
1
)(()
|
0
|