Ural 1745 Yet Another Answer

时间限制:10s      空间限制:64MB

题目描述

外星人制造了超级电脑来思考生命,宇宙,以及世界万物的答案,最后得出了42这个结果。人们并不满意于这个答案,于是再一次设计了超级电脑。经历了π百万年的计算,再一次得出了新的答案。

答案是由一些字符串组成的,每个字符串都只包含“(”和“)”两种字符。

现在的问题是,从这些字符串中选取一些,按照一定的顺序连接起来,使得构成一个合法的括号序列而且长度尽量长。


输入格式

本题存在多组数据,请做到文件底结束,任两组数据间存在一空行
第一行正整数 N (1 ≤ N ≤ 1,000).表示字符串个数。
接下来N行每行一个字符串。总长度不超过10,000。(编号1到N)


输出格式

对于每组数据输出最大长度


样例输入

3
()
(()
)

样例输出

6

提示

样例解释

(())()


题目来源

没有写明来源

Menuappsclose