CF1598F.RBS

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.

括号序列是指仅由字符 ( 和 ) 组成的字符串。正则括号序列（简称 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 的前缀。

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$.

第一行包含一个整数 $n$（$1 \le n \le 20$）。

接下来有 $n$ 行，其中第 $i$ 行包含字符串 $s_i$ —— 一个括号序列（由字符 "(" 和/或 ")" 组成的字符串）。所有序列 $s_i$ 均非空，且它们的总长度不超过 $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.

输出一个整数——字符串 $s_1 + s_2 + \dots + s_n$ 的非空前缀中，合法括号序列（RBS）的最大可能数量，其中字符串 $s_1, s_2, \dots, s_n$ 可以以任意顺序重新排列。

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.

在第一个例子中，你可以按如下方式连接字符串："(" $+$ ")" $=$ "()"，所得字符串将有一个前缀是正则括号序列（RBS）："()"。

在第二个例子中，你可以按如下方式连接字符串："(" $+$ ")" $+$ "()()())" $+$ "(" $=$ "()()()())("，所得字符串将有四个前缀是正则括号序列（RBS）："()"、"()()"、"()()()"、"()()()()"。

第三和第四个例子中各自仅包含一个字符串，因此顺序是固定的。