有一天,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
注意
在第一个示例中,最好构造两对:“(( )())”和“( )”。