CF1097C Yuhao and a Parenthesis

有一天，Yuhao 遇到了一个关于判断括号序列是否合法的问题。 括号序列是由左括号和右括号组成的任意非空序列。如果可以通过在该序列中插入字符 “+” 和 “1” 得到一个合法的算术表达式，则称该括号序列为合法括号序列。例如，序列 “(())()”、“()” 和 “(()(()))” 是合法的，而 “)(”、“(()” 和 “(()))(” 不是合法的括号序列。 Yuhao 觉得这个问题太简单了，于是他决定让问题变得更难。现在给你许多（不一定合法的）括号序列。你的任务是将其中的一些括号序列两两配对，使得每个括号序列最多只出现在一个配对中，并且每对配对中两个括号序列拼接后的结果是一个合法的括号序列。目标是使配对的数量尽可能多。 然而，这个问题对 Yuhao 来说太难了。你能帮他解决这个问题吗？

第一行包含一个整数 $n$（$1 \leq n \leq 10^5$），表示括号序列的数量。 接下来的 $n$ 行，每行包含一个括号序列——一个只由 “(” 和 “)” 组成的非空字符串。 所有括号序列的长度之和不超过 $5 \cdot 10^5$。 注意，一个括号序列在输入中可能出现多次。在这种情况下，你可以分别使用每一个副本。还要注意，输入字符串出现的顺序无关紧要。

输出一个整数，表示在满足题目条件的情况下，最多可以配对的数量。

在第一个样例中，最优的做法是构造两对配对：“(())()” 和 “()”。 由 ChatGPT 4.1 翻译