P16142 [ICPC 2017 NAIPC] Pieces of Parentheses

你正在教授一门编程课程，想要讲解括号匹配的内容。你准备了一个很好的视觉辅助工具——一块写有很长且括号匹配的字符串的牌子。但可惜的是，不知怎的，你的视觉辅助工具被摔成了碎片，可能还有一些碎片丢失了！你得尽力把它重新拼好。给定每个碎片上的括号字符串，请问通过按某种顺序拼接其中一些碎片（每个碎片最多使用一次，且碎片不可反转），你能得到的最长的括号匹配字符串的长度是多少？ 括号匹配字符串的定义如下： 1. 空字符串 2. $AB$，其中 $A$ 和 $B$ 都是括号匹配字符串 3. $(A)$，其中 $A$ 是括号匹配字符串

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。输入的第一行包含一个整数 $n$（$1 \leq n \leq 300$），表示碎片的数量。 接下来的 $n$ 行，每行包含一个字符串 $s$（$1 \leq |s| \leq 300$），仅由字符 '(' 和 ')' 组成。这表示其中一块碎片。

输出一个整数，表示你能从这些碎片中拼接出的最长括号匹配字符串的长度。注意，空字符串在技术上也属于括号匹配字符串，因此总是可以得到长度至少为 0 的字符串（尽管空字符串作为视觉辅助工具效果并不好！）。

翻译由 DeepSeek V3.2 完成