← 返回题目列表

Codeforces · 1097/C

C. 雨浩和括号

中文机器翻译题面 查看原题

有一天,Yuhao 遇到了一个问题,关于检查某些括号序列是否正确的括号序列。

括号序列是左括号和右括号的任何非空序列。如果可以通过在该序列中插入字符“+”和“1”来获得正确的算术表达式,则该括号序列称为正确的括号序列。例如,序列“(())()”、“()”和“(()(()))”是正确的,而括号序列“)(”、“(()”和“(()))(”是不正确的。

雨浩觉得这个问题对他来说太简单了,所以他决定让这个问题变得更难。您会得到许多(不一定是正确的)括号序列。任务是将其中一些括号序列连接成有序对,使得每个括号序列最多出现在一对中,并且每对中的括号序列的串联是正确的括号序列。目标是创建尽可能多的配对。

不幸的是,这个问题对于雨浩来说太难了。你能帮助他并解决这个问题吗?

输入

第一行包含一个整数 $$$n$$$ ($$$1 \leq n \leq 10^5$$$) — 括号序列的数量。

以下 $$$n$$$ 行中的每一行都包含一个括号序列 — 一个仅由字符“(”和“)”组成的非空字符串。

输入中所有括号序列的长度之和最多为 $$$5 \cdot 10^5$$$。

请注意,括号序列可能会在输入中多次出现。在这种情况下,您可以单独使用序列的每个副本。另请注意,字符串在输入中出现的顺序并不重要。

输出

打印单个整数 — 根据语句中的条件可以形成的最大对数。

示例

输入 #1

7
)())
)
((
((
(
)
)

输出 #1

2

输入 #2

4
(
((
(((
(())

输出 #2

0

输入 #3

2
(())
()

输出 #3

1

注意

在第一个示例中,最好构造两对:“((     )())”和“(     )”。