括号序列是仅包含字符“(”和“)”的字符串。常规括号序列(或者简称为 RBS)是可以通过在序列的原始字符之间插入字符“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$$$ 具有尽可能多的 RBS 非空前缀。
输入
第一行包含一个整数 $$$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$$$ 的 RBS 非空前缀的最大数量。
示例
输入 #1
2 ( )
输出 #1
1
输入 #2
4 ()()()) ( ( )
输出 #2
4
输入 #3
1 (())
输出 #3
1
输入#4
1 )(()
输出#4
0
注意
在第一个示例中,您可以按如下方式连接字符串:“(” $$$+$$$ “)” $$$=$$$ “()”,生成的字符串将有一个前缀,即 RBS:“()”。
在第二个示例中,您可以按如下方式连接字符串: "(" $$$+$$$ ")" $$$+$$$ "()()())" $$$+$$$ "(" $$$=$$$ "()()()())(",生成的字符串将有四个 RBS 前缀:“()”、 “()()”、“()()()”、“()()()()”。
第三个和第四个示例各仅包含一个字符串,因此顺序是固定的。