CF1598F 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).