One day, Yuhao came across a problem about checking if some bracket sequences are correct bracket sequences.

A bracket sequence is any non-empty sequence of opening and closing parentheses. A bracket sequence is called a correct bracket sequence if it's possible to obtain a correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, the sequences "(())()", "()" and "(()(()))" are correct, while the bracket sequences ")(", "(()" and "(()))(" are not correct.

Yuhao found this problem too simple for him so he decided to make the problem harder. You are given many (not necessarily correct) bracket sequences. The task is to connect some of them into ordered pairs so that each bracket sequence occurs in at most one pair and the concatenation of the bracket sequences in each pair is a correct bracket sequence. The goal is to create as many pairs as possible.

This problem unfortunately turned out to be too difficult for Yuhao. Can you help him and solve it?


-----Input-----

The first line contains one integer $n$ ($1 \leq n \leq 10^5$) — the number of bracket sequences.

Each of the following $n$ lines contains one bracket sequence — a non-empty string which consists only of characters "(" and ")".

The sum of lengths of all bracket sequences in the input is at most $5 \cdot 10^5$.

Note that a bracket sequence may appear in the input multiple times. In this case, you can use each copy of the sequence separately. Also note that the order in which strings appear in the input doesn't matter.


-----Output-----

Print a single integer — the maximum number of pairs which can be made, adhering to the conditions in the statement.


-----Examples-----
Input
7
)())
)
((
((
(
)
)

Output
2

Input
4
(
((
(((
(())

Output
0

Input
2
(())
()

Output
1



-----Note-----

In the first example, it's optimal to construct two pairs: "((     )())" and "(     )".

Difficulty: interview

Starter code:

Solutions:
n = int(input())

ls = [input() for _ in range(n)]

balance = [[0, 0] for _ in range(n)]

for i in range(n):
	for j in range(len(ls[i])):
		balance[i][0] = balance[i][0] + (1 if ls[i][j] == '(' else -1)
		balance[i][1] = min(balance[i][1], balance[i][0])

balance2 = []

for i in range(n):
	if balance[i][0] < 0:
		if balance[i][1] >= balance[i][0]:
			balance2.append(balance[i][0])
	if balance[i][0] >= 0:
		if balance[i][1] >= 0:
			balance2.append(balance[i][0])

balance2.sort()


answer = 0

i, j = 0, len(balance2) - 1

while i < j:
	if balance2[i] + balance2[j] == 0:
		answer += 1
		i += 1
		j -= 1
	elif balance2[i] + balance2[j] < 0:
		i += 1
	elif balance2[i] + balance2[j] > 0:
		j -= 1 

print(answer)





n = int(input())


starts = []
ends = []
fulls = 0
#Testing Validity
for _ in range(n):
    s = input()
    count = 0
    mn = 0
    for c in s:
        if c == '(':
            count += 1
        else:
            count -= 1
            mn = min(mn, count)
    #print(count, mn)

    if count > 0:
        if mn == 0:
            starts.append(count)
    elif count < 0:
        if mn == count:
            ends.append(-1 * count)
    else:
        if mn == 0:
            fulls += 1

starts.sort()
ends.sort()

out = 0
while len(starts) > 0 and len(ends) > 0:
    st = starts[0]
    en = ends[0]

    if st < en:
        starts.pop(0)
    elif st > en:
        ends.pop(0)
    else:
        out += 1
        starts.pop(0)
        ends.pop(0)

print(out + fulls//2)
            
        
        


N = int(input())
L = {}
R = {}
Z = 0
ans = 0
for i in range(N):
    s = input()
    ok = 1
    cnt = 0
    for c in s:
        if c == '(':
            cnt += 1
        else:
            if cnt == 0:
                ok = 0
                break
            cnt -= 1
    if ok:
        if cnt == 0:
            if Z == 1:
                ans += 1
            Z ^= 1
        else:
            if R.get(cnt, 0) > 0:
                ans += 1
                R[cnt] -= 1
            else:
                L[cnt] = L.get(cnt, 0) + 1
        continue

    ok = 1
    for c in reversed(s):
        if c == ')':
            cnt += 1
        else:
            if cnt == 0:
                ok = 0
                break
            cnt -= 1
    if ok:
        if cnt == 0:
            if Z == 1:
                ans += 1
            Z ^= 1
        else:
            if L.get(cnt, 0) > 0:
                ans += 1
                L[cnt] -= 1
            else:
                R[cnt] = R.get(cnt, 0) + 1
print(ans)

n = int(input())
strs = []
for i in range(n):
    strs.append(input())

def check(s):
    h = 0
    min_h = max_h = 0
    s = s.strip()
    for c in s:
        if c == '(':
            h += 1
        elif c == ')':
            h -= 1
        else:
            raise NotImplementedError()

        min_h = min(h, min_h)
        max_h = max(h, max_h)

    if min(0, h) == min_h:
        return h
    else:
        return None

def count_pairs(strs):
    by_height = {}
    for s in strs:
        h = check(s)
        if h not in by_height:
            by_height[h] = 0
        by_height[h] += 1

    pairs_count = 0
    for h, c in list(by_height.items()):
        if h is not None and h > 0:
            pairs_count += min(by_height[h], by_height.get(-h, 0))

    pairs_count += by_height.get(0, 0) // 2
    return pairs_count

print(count_pairs(strs))


def ii():
    return int(input())
def mi():
    return list(map(int, input().split()))
def li():
    return list(mi())
MAX = 6 * 10 ** 5

n = ii()
a = [input().strip() for i in range(n)]
pos = [[] for i in range(MAX)]
neg = [[] for i in range(MAX)]
for s in a:
    p = m = 0
    for c in s:
        if c == '(':
            p += 1
        else:
            p -= 1
        m = min(m, p)
    if p >= 0:
        pos[p].append(m)
    else:
        neg[-p].append(m)

ans = 0
for p in range(1, MAX):
    c1 = sum(x >= 0 for x in pos[p])
    c2 = sum(x + p >= 0 for x in neg[p])
    ans += min(c1, c2)
c3 = sum(x >= 0 for x in pos[0])
ans += c3 // 2
print(ans)


from collections import Counter
def cal(x):
    left = cl = 0
    for i in x:
        if i == "(":
            cl += 1
        if i == ")":
            if cl <= 0:
                left += 1
            else:
                cl -= 1
    return left, cl
n = int(input())
a = [*[x for x in [cal(input()) for i in range(n)] if x[0] == 0 or x[1] == 0]]
left = Counter([i[1] for i in [x for x in a if x[0] == 0]])
right = Counter([i[0] for i in [x for x in a if x[1] == 0]])
ans = 0
#print(left, right)
for i in list(left.keys()):
    ans += (min(left[i], right[i]) if i != 0 else left[i] // 2)
print(ans)





MOD = 10**9 + 7
I = lambda:list(map(int,input().split()))

def find(s):
    r = []
    for i in s[::-1]:
        if i == '(':
            r.append(')')
    return ''.join(r) if len(r) == len(s) else False

def pre(s):
    k = [1]
    for i in s:
        if i == ')' and k[-1] == '(':
            k.pop()
        else:
            k.append(i)
    return ''.join(k[1:])

n, = I()
d = {'a':0}
l = []
for i in range(n):
    s = input()
    s = pre(s)
    l.append(s)
    if not s:
        d['a'] += 1
    elif s in d:
        d[s] += 1
    else:
        d[s] = 1
count = 0
l.sort(key = lambda x:len(x))
for i in l:
    k = find(i)
    if i and i[0] != ')' and k in d and d[k] > 0:
        count += 1
        d[k] -= 1
        d[i] -= 1
count += d['a']//2
print(count)

cs = int(input())


open = []
clos = []
val = 0
for c in range(cs):
    brac = input()
    
    s = []
    for b in brac:
        if len(s) == 0 or b == '(':
            s.append(b)
        else:
            if s[-1] == '(':
                s.pop()
            else:
                s.append(')')
                
    if len(s) != 0:
        if s[0] == s[-1] == '(':
            open.append(len(s))
        if s[0] == s[-1] == ')':
            clos.append(len(s))
    else:
        val += 1 

close = dict()

for cl in clos:
    if cl not in close:
        close[cl] = 1
    else:
        close[cl] += 1
ans = val // 2
for op in open:
    if op in close:
        ans += 1
        close[op] -= 1
        if close[op] == 0:
            del close[op]
print(ans)            
            


from collections import Counter
N = int(input())
S = [input() for i in range(N)]
c1 = Counter()
c2 = Counter()
zeros = 0

for s in S:
    op = nop = 0
    for c in s:
        if c == '(':
            op += 1
        else:
            if op == 0:
                nop += 1
            else:
                op -= 1
    if op and nop: continue
    if op:
        c1[op] += 1
    elif nop:
        c2[nop] += 1
    else:
        zeros += 1

print(sum((c1&c2).values()) + zeros//2)


from collections import defaultdict

def solve():
    n = int(input())
    seqs = defaultdict(list)
    for _ in range(n):
        seq = input()
        seq = [1 if c == '(' else -1 for c in seq]
        cumm_sum = [0 for _ in range(len(seq)+1)]
        for i in range(len(seq)):
            cumm_sum[i+1] = seq[i] + cumm_sum[i]

        value = sum(seq)
        height = min(cumm_sum)

        if value >= 0 and height < 0:
            continue
        if value < 0 and height < value:
            continue

        seqs[value].append(height)

    num_pairs = 0
    for val in seqs:
        if val < 0: continue
        if val == 0: num_pairs += len(seqs[val]) // 2
        if val > 0 and (-val) in seqs:
            num_pairs += min(len(seqs[val]), len(seqs[-val]))

    print(num_pairs)

solve()




n = int(input())
# by count of opens
a = dict()
for pos in range(n):
    cur = input()
    ops = 0
    add = 0
    was = False
    for i in cur:
        if i == '(':
            ops += 1
            add += 1
        else:
            ops -= 1
            if ops < 0:
                was = True
            add = max(add - 1, 0)
    if was and add > 0:
        continue
    if ops in a:
        a[ops] += 1
    else:
        a[ops] = 1

ans = 0
for i in list(a.keys()):
    if (0 - i) in a:
        if i != 0:
            cur = min(a[i], a[0 - i])
            ans += cur
            a[i] -= cur
            a[0 - i] -= cur
        else:
            ans += a[0] // 2
print(ans)


import collections

def rev(l):
	ret = ""
	for ch in l[::-1]:
		ret = ret + ("(" if ch == ")" else ")")
	return ret
	
def cnt(l):
	ret = cntimpl(l)
	if ret is None:
		ret = cntimpl(rev(l))
		if ret is not None:
			ret *= -1
	return ret

def cntimpl(l):
	q = 0
	for ch in l:
		if ch == "(":
			q += 1
		else:
			q -= 1
			if q < 0:
				return None
	return q

###

n = int(input())
s = [input() for _ in range(n)]

#print(n, s)

v = [cnt(x) for x in s]

#print(v)

v = [x for x in v if x is not None]
v.sort()
v = collections.deque(v)

#print(v)

ans = 0
while len(v) > 1:
	if v[0] == -v[-1]:
		ans += 1
		v.pop()
		v.popleft()
	elif abs(v[0]) > abs(v[-1]):
		v.popleft()
	else:
		v.pop()

print(ans)

import sys 

Ans = 0
N = int(input())
left = {}
right = {}
correct = 0

for i in range(N):
    arr = sys.stdin.readline().strip()
    check = []

    for j in arr:
        if len(check)==0:
            check.append(j) 
        elif j == ")" and check[-1] == "(":
            check.pop() 
        else:
            check.append(j)

    leftnum = check.count("(")
    rightnum = check.count(")")
    if  leftnum > 0 and rightnum > 0:
        continue
    elif leftnum > 0:
        try:
            left[ str(leftnum) ] += 1
        except:
            left[ str(leftnum) ] = 1

    elif rightnum > 0:
        try:
            right[ str(rightnum) ] += 1
        except:
            right[ str(rightnum) ] = 1
    else:
        correct += 1


Ans += correct // 2

for key, value in list(left.items()):
    try:
        Ans += min( right[key], value )
    except:
        pass 
    

print ( Ans )


n = int(input())

d = {}

for i in range(n):
    s = input()
    k = 0
    pr = True
    suf = True
    for j in s:
        if j == '(':
            k +=1
        else:
            k -=1
        if k < 0:
            pr = False
    k = 0
    for j in reversed(s):
        if j == '(':
            k +=1
        else:
            k -= 1
        if k > 0:
            suf = False
    if (k > 0 and pr) or (k == 0 and pr and suf) or (k < 0 and suf):
        if k not in d:
            d[k] = 0
        d[k] += 1

ans = 0
if 0 in d:
    ans += d[0] // 2
    del d[0]
for k in d:
    if d[k] <= 0:
        continue
    if -k in d and d[-k] > 0:
        mn = min(d[k], d[-k])
        d[k] -= mn
        d[-k] -= mn
        ans += mn
print(ans)


import sys
input = sys.stdin.readline

n=int(input())
B=[input().strip() for i in range(n)]

LIST=[]

for b in B:
    care=0

    BRSUM=0
    for bb in b:
        if bb==")":
            BRSUM-=1
        else:
            BRSUM+=1

        if BRSUM<0:
            care=min(care,BRSUM)

    if care<0 and BRSUM>care:
        continue
    else:
        LIST.append(BRSUM)

from collections import Counter
counter=Counter(LIST)

ANS=0
for l in sorted(list(counter.keys())):
    if l==0:
        ANS+=counter[l]//2
        break
    
    if l>0:
        break

    ANS+=min(counter[l],counter[-l])


print(ANS)

        


from collections import Counter

c1 = Counter()
c2 = Counter()
for _ in range(int(input())):
    s = input()
    p = 0
    q = 0
    for c in s:
        if c == "(":
            p += 1
        else:
            p -= 1
            q = min(q, p)
    if p == q:
        c1[-p] += 1
    elif q == 0:
        c2[p] += 1
print(sum((min(c1[k], c2[k]) for k in list(c1.keys()))) + c1[0] // 2)


import collections

def pos_score(S):
    s = 0
    for c in S:
        if c == '(':
            s += 1
        elif c == ')':
            s -= 1
        if s < 0:
            return None
    return s

def neg_score(S):
    s = 0
    for c in reversed(S):
        if c == '(':
            s += 1
        elif c == ')':
            s -= 1
        if s > 0:
            return None
    return s

def score(S):
    p = pos_score(S)
    if p is not None:
        return p
    n = neg_score(S)
    if n is not None:
        return n
    return None

N = int(input())
scores = [score(input()) for _ in range(N)]
score_neg_map = collections.Counter(-sc for sc in scores if sc is not None and sc < 0)
score_pos_map = collections.Counter(sc for sc in scores if sc is not None and sc > 0)
score_zero = sum(sc == 0 for sc in scores)

ans = score_zero // 2
for key in score_pos_map:
    pos = score_pos_map[key]
    neg = score_neg_map.get(key, 0)
    ans += min(pos, neg)
print(ans)


from collections import defaultdict as dd
d = dd(int)

n = int(input())
for i in range(n):
    s = input()
    f = 0
    ff = 0
    for j in range(len(s)):
        if s[ j ] == '(':
            f += 1
        elif s[ j ] == ')':
            f -= 1
        if f < 0:
            ff += 1
            f = 0
    if f == 0:
        d[ -ff ] += 1
    elif ff == 0:
        d[ f ] += 1

s = d[ 0 ] // 2
for k, v in list(d.items()):
    if k > 0:
        s += min( d[ k ], d[ -k ] )

print( s )




from collections import Counter

def cleanup(paren: str) -> str:
    stack = list()

    for char in paren:
        if not stack:
            stack.append(char)
        elif stack[-1] == '(' and char == ')':
            stack.pop()
        else:
            stack.append(char)

    return ''.join(stack)
    
def main():
    prob_len = int(input())

    lefts = Counter()
    rights = Counter()
    zeros = 0
    for _ in range(prob_len):
        new_paren = cleanup(input())
        if '(' in new_paren and ')' in new_paren:
            continue
        elif '(' in new_paren:
            lefts.update([len(new_paren)])
        elif ')' in new_paren:
            rights.update([len(new_paren)])
        else:
            zeros += 1

    answer = 0
    answer += zeros // 2
    for paren_num in lefts.keys():
        answer += min(lefts[paren_num], rights[paren_num])

    print(answer)

def __starting_point():
    main()
__starting_point()

# -*- coding: utf-8 -*-
# @Time    : 2019/1/4 23:10
# @Author  : LunaFire
# @Email   : gilgemesh2012@gmail.com
# @File    : C. Yuhao and a Parenthesis.py


def calc_bracket(sequence):
    left_num, right_num = 0, 0
    for c in sequence:
        if c == ')':
            if left_num != 0:
                left_num -= 1
            else:
                right_num += 1
        else:
            left_num += 1
    return left_num, right_num


def main():
    total_num = int(input())

    result = 0
    left_dict, right_dict = {}, {}
    correct_num = 0

    for _ in range(total_num):
        sequence = input()
        left_num, right_num = calc_bracket(sequence)
        if left_num != 0 and right_num != 0:
            continue
        elif left_num:
            if right_dict.get(left_num, 0):
                right_dict[left_num] -= 1
                result += 1
            else:
                left_dict[left_num] = left_dict.get(left_num, 0) + 1
        elif right_num:
            if left_dict.get(right_num, 0):
                left_dict[right_num] -= 1
                result += 1
            else:
                right_dict[right_num] = right_dict.get(right_num, 0) + 1
        else:
            correct_num += 1

    result = result + correct_num // 2
    print(result)


def __starting_point():
    main()

__starting_point()

n = int(input())

left = {}
right = {}
neutral_count = 0

for _ in range(n):
    bracket = input()
    s = []
    for p in bracket:
        if '(' == p:
            s.append('(')
        if ')' == p:
            if len(s) > 0 and s[-1] == '(':
                s.pop()
            else:
                s.append(')')
    if len(s) == 0:
        neutral_count += 1
    elif all(e == '(' for e in s):
        l = len(s)
        if l in left:
            left[l] += 1
        else:
            left[l] = 1
    elif all(e == ')' for e in s):
        r = len(s)
        if r in right:
            right[r] += 1
        else:
            right[r] = 1
ans = 0
ans += neutral_count//2
for l in left:
    r = 0
    if l in right:
        r = right[l]
    ans += min(left[l], r)
print(ans) 




n=int(input())
skobs1=dict()
skobs2=dict()
ptav_cnt=0
for t in range(n):
    skob=input()
    fl=2
    opcnt=0
    clcnt=0
    opcnt2=0
    clcnt2=0
    for s in range(len(skob)):
        if skob[s]==')':
            clcnt+=1
        else:
            opcnt+=1
        if clcnt>opcnt:
            fl=1
    for s in range(len(skob)-1,-1,-1):
        if skob[s]==')':
            clcnt2+=1
        else:
            opcnt2+=1
        if clcnt2<opcnt2 and fl==1:
            fl=0
    if fl:
        if opcnt==clcnt:
            ptav_cnt+=1
        elif opcnt>clcnt:
            if opcnt-clcnt in skobs1:
                skobs1[opcnt-clcnt]+=1
            else:
                skobs1[opcnt - clcnt] = 1
        else:
            if clcnt-opcnt in skobs2:
                skobs2[clcnt - opcnt]+=1
            else:
                skobs2[clcnt - opcnt] = 1
ans=ptav_cnt//2
for t in skobs1:
    if t in skobs2:
        ans+=min(skobs1[t],skobs2[t])
print(ans)






def score(x):
    s = []
    for i in x:
        if len(s) == 0:
            s.append(i)
            continue
        h = s[-1]
        if h == '(' and i == ')':
            s.pop()
        else:
            s.append(i)
    if '(' in s and ')' in s:
        return None
    if '(' in s:
        return len(s)
    else:
        return -1 * len(s)

n = int(input())
a = []
for _ in range(n):
    x = input()
    a.append(x)
    
d = {}
for i in a:
    j = score(i)
    if j != None:
        if j in d:
            d[j] += 1
        else:
            d[j] = 1

c = 0
for i in d:
    if i == 0:
        c += d[i] // 2
    else:
        if -i in d and d[i] > 0 and d[-i] > 0:
            x = min(d[i], d[-i])
            d[i] -= x
            d[-i] -= x
            c += x
print(c)


import sys

#fin  = open("C.in", "r")
fin = sys.stdin

n = int(fin.readline())
A = []
for i in range(n): 
	A += [fin.readline()[:-1]]

sg = {'(' : +1, ')' : -1}
INF = 2000000000

def analyze(s):
	sm = 0
	mn = 0
	for ch in s:
		sm += sg[ch]
		mn = min(mn, sm)

	if (sm >= 0 and mn < 0): return INF
	if (sm < 0 and sm != mn): return INF

	return sm

d = {}
for s in A:
	t = analyze(s)
	if (t == INF): continue

	if (t in d): d[t] += 1
	else: d[t] = 1

ans = 0
for a in d:
	if (a > 0 and (-a) in d): ans += min(d[a], d[-a])

if (0 in d): ans += d[0]//2

print(ans)






n = int(input())
a = [input() for i in range(n)]
kk = {}
for i in a:
    if i[0] == ')' and i[-1] == '(':
        continue
    cnt = 0
    flag1 = False
    flag2 = False
    isFirst = False
    for j in i:
        if j == '(':
            cnt += 1
        else:
            cnt -= 1
        if cnt > 0:
            flag1 = True
            if not flag2:
                isFirst = True
        if cnt < 0:
            flag2 = True
    flag = False
    if cnt == 0:
        if flag2:
            continue
        else:
            flag = True
    if cnt > 0:
        if flag2:
            continue
        else:
            flag = True
    if cnt < 0:
        cnt_zakr = 0
        for j in i[::-1]:
            if j == '(':
                cnt_zakr -= 1
                if cnt_zakr < 0:
                    break
            else:
                cnt_zakr += 1
        else:
            flag = True
    if not flag:
        continue
    kk[cnt] = kk.get(cnt, 0) + 1
#print(kk)
ans = 0
for i in kk.keys():
    if i >= 0:
        continue
    a = kk[i]
    b = kk.get(-i, 0)
    ans += min(a, b)
ans += kk.get(0, 0) // 2
print(ans)