← 返回题目列表

Codeforces · 1598/F

F. 苏格兰皇家银行

中文机器翻译题面 查看原题

括号序列是仅包含字符“(”和“)”的字符串。常规括号序列(或者简称为 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 前缀:“()”、 “()()”、“()()()”、“()()()()”。

第三个和第四个示例各仅包含一个字符串,因此顺序是固定的。