RBS

题意翻译

### 题目描述 定义括号序列为只包括 $\texttt{(}$ 和 $\texttt{)}$ 的字符串。一个匹配的括号序列（简记为 RBS）满足，可以在其中加入 $1$ 和 $+$，将其转化为合法的代数式，例如： + $\texttt{()()}$ 和 $\texttt{(())}$ 是匹配的 + $\texttt{)(}$ 和 $\texttt{(}$ 和 $\texttt{)}$ 不是。 将两个字符串拼接在一起简记为 $x+y$。例如，$\texttt{()()}+\texttt{)(}=\texttt{()())(}$。 给定 $n$ 个括号序列 $s_1\sim s_n$，你可以将他们任意重新排序，要求使得最终排序后的字符串满足 $s_1+\dots+s_n$ 的 RBS 前缀个数最多。 ### 输入格式 第一行包含一个正整数 $n$（$1\le n\le 20$）。 接下来的 $n$ 行，每行包含一个括号序列，第 $i+1$ 行输入的是 $s_i$。保证 $s_i$ 的总长度不超过 $4\cdot 10^5$。 ### 输出格式 输出一个整数，表示最大 RBS 前缀长度。 ### 说明/提示 在第一个样例中，你可以将字符串拼接为 $\texttt{(}+\texttt{)}=\texttt{()}$，此时 RBS 前缀个数为 $1$，就是 $\texttt{()}$。 在第二个样例中，你可以将字符串凭借为 $\texttt(+\texttt)+\texttt{()()())}+\texttt{(}=\texttt{()()()())(}$，此时 RBS 前缀个数为 $4$，就是 $\texttt{()}$、$\texttt{()()}$、$\texttt{()()()}$ 和 $\texttt{()()()()}$。 第三个和第四个样例中仅有一个字符串，因此顺序是固定的。 Translated by [hodf](https://www.luogu.com.cn/user/121027).

题目描述

A bracket sequence is a string containing only characters "(" and ")". A regular bracket sequence (or, shortly, an RBS) is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example: - bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)"); - bracket sequences ")(", "(" and ")" are not. Let's denote the concatenation of two strings $ x $ and $ y $ as $ x+y $ . For example, "()()" $ + $ ")(" $ = $ "()())(". You are given $ n $ bracket sequences $ s_1, s_2, \dots, s_n $ . You can rearrange them in any order (you can rearrange only the strings themselves, but not the characters in them). Your task is to rearrange the strings in such a way that the string $ s_1 + s_2 + \dots + s_n $ has as many non-empty prefixes that are RBS as possible.

输入输出格式

输入格式

The first line contains a single integer $ n $ ( $ 1 \le n \le 20 $ ). Then $ n $ lines follow, the $ i $ -th of them contains $ s_i $ — a bracket sequence (a string consisting of characters "(" and/or ")". All sequences $ s_i $ are non-empty, their total length does not exceed $ 4 \cdot 10^5 $ .

输出格式

Print one integer — the maximum number of non-empty prefixes that are RBS for the string $ s_1 + s_2 + \dots + s_n $ , if the strings $ s_1, s_2, \dots, s_n $ can be rearranged arbitrarily.

输入输出样例

输入样例 #1

2
(
)

输出样例 #1

1

输入样例 #2

4
()()())
(
(
)

输出样例 #2

4

输入样例 #3

1
(())

输出样例 #3

1

输入样例 #4

1
)(()

输出样例 #4

0

说明

In the first example, you can concatenate the strings as follows: "(" $ + $ ")" $ = $ "()", the resulting string will have one prefix, that is an RBS: "()". In the second example, you can concatenate the strings as follows: "(" $ + $ ")" $ + $ "()()())" $ + $ "(" $ = $ "()()()())(", the resulting string will have four prefixes that are RBS: "()", "()()", "()()()", "()()()()". The third and the fourth examples contain only one string each, so the order is fixed.