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: MEDIUM
Tags: Implementation

Greedy algorithms
Skill types: Greedy algorithms

Starter code:

Solutions:
n = int(input())
parr = {}
narr = {}
zero = 0
ans = 0
for i in range(n):
	s = input()
	x = 0
	y = 0
	left = True
	right = True
	for j in range(len(s)):
		if s[j] == '(':
			x += 1
		else:
			x -= 1
		if x < 0:
			left = False
		if s[-1 * (j + 1)] == '(':
			y += 1
		else:
			y -= 1
		if y > 0:
			right = False
	if left and right and (x == 0):
		zero += 1
	elif left or right:
		if x > 0:
			parr[x] = parr.get(x, 0) + 1
		else:
			narr[x] = narr.get(x, 0) + 1
ans += zero // 2
for i in narr.keys():
	ans += min(narr[i], parr.get(-i, 0))
print(ans)


N = int(input())
zerocount = 0
tzero = []
tarr = [0]
s = []
larr = [0 for i in range(5 * 10 ** 5 + 100)]
rarr = [0 for i in range(5 * 10 ** 5 + 100)]
for i in range(N):
	s.append(input())
s = sorted(s)
for i in range(N):
	left = 0
	right = 0
	for j in range(len(s[i])):
		if s[i][j] == '(':
			left += 1
		if s[i][j] == ')':
			if left > 0:
				left -= 1
			else:
				right += 1
	if left == 0 and right == 0:
		zerocount += 1
	else:
		if left == 0 and right > 0:
			rarr[right] += 1
		if right == 0 and left > 0:
			larr[left] += 1
ans = 0
if zerocount > 1:
	ans += zerocount // 2
for i in range(5 * 10 ** 5 + 1):
	ans += min(larr[i], rarr[i])
print(ans)


import sys
from itertools import accumulate
from collections import Counter
n = int(input())
a = [list(accumulate((1 if c == '(' else -1 for c in l.rstrip()))) for l in sys.stdin]
counter = Counter((acc[-1] for acc in a if min(acc) == acc[-1] < 0 or min(acc) >= 0))
ans = 0
for (k, v) in counter.items():
	if k < 0:
		ans += min(v, counter[-k])
	elif k == 0:
		ans += v // 2
print(ans)


def solve(arr, n):
	mx = 10 ** 6
	pos = [0] * mx
	neg = [0] * mx
	for br in arr:
		sm = 0
		mn = 0
		for it in br:
			if it == '(':
				sm += 1
			else:
				sm -= 1
				if sm < mn:
					mn = sm
		if sm >= 0 and mn == 0:
			pos[sm] += 1
		elif sm < 0 and sm == mn:
			neg[-sm] += 1
	res = pos[0] // 2
	for i in range(1, mx):
		res += min(pos[i], neg[i])
	print(res)
n = int(input())
arr = []
for i in range(n):
	t = input()
	arr.append(t)
solve(arr, n)


n = int(input())
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 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)


from collections import Counter
n = int(input())
c = Counter()

def good_for_front(s):
	cnt = 0
	for i in range(len(s)):
		if s[i] == '(':
			cnt += 1
		else:
			cnt -= 1
		if cnt < 0:
			return False
	return True

def good_for_back(s):
	cnt = 0
	for i in range(len(s) - 1, -1, -1):
		if s[i] == ')':
			cnt += 1
		else:
			cnt -= 1
		if cnt < 0:
			return False
	return True

def score(s):
	return 2 * s.count('(') - len(s)
for _ in range(n):
	s = input()
	if good_for_front(s) and good_for_back(s):
		c[0] += 1
	elif good_for_front(s):
		c[score(s)] += 1
	elif good_for_back(s):
		c[score(s)] += 1
ans = 0
for key in c.keys():
	if key == 0:
		ans += c[key] // 2
	elif key > 0:
		ans += min(c[key], c[-key])
print(ans)


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())
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
		elif 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)


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 c1.keys())) + c1[0] // 2)


n = int(input())
openingArr = []
closingArr = []
total = 0
k = 0
for i in range(n):
	st = str(input())
	t = 0
	ope = 0
	close = 0
	for j in st:
		if j == ')':
			if ope > 0:
				ope -= 1
			else:
				close += 1
		elif j == '(':
			ope += 1
	if ope is 0 and close is not 0:
		closingArr.append(close)
	elif ope is not 0 and close is 0:
		openingArr.append(ope)
	elif ope is 0 and close is 0:
		k += 1
total += k // 2
if len(openingArr):
	openingArr.sort()
else:
	print(total)
	quit()
if len(closingArr):
	closingArr.sort()
else:
	print(total)
	quit()
i = 0
j = 0
while i < len(openingArr) and j < len(closingArr):
	if openingArr[i] == closingArr[j]:
		total += 1
		i += 1
		j += 1
	elif openingArr[i] > closingArr[j]:
		j += 1
	else:
		i += 1
print(total)


_M = 500001
n = int(input())
a = []
d = {x: [] for x in range(-_M, _M)}
for _ in range(n):
	b = input()
	s = []
	f = True
	for i in range(len(b)):
		if b[i] == '(':
			if i == 0:
				s.append(1)
			else:
				s.append(s[i - 1] + 1)
		elif b[i] == ')':
			if i == 0:
				s.append(-1)
			else:
				s.append(s[i - 1] - 1)
		if s[len(s) - 1] < 0:
			f = False
	a.append(s)
	x = s[len(s) - 1]
	if x < 0 or f:
		d[x].append(s)
s = 0
s += len(d[0]) // 2
for k in range(1, _M):
	while len(d[-k]) > 0 and len(d[k]) > 0:
		f = True
		for x in d[-k][len(d[-k]) - 1]:
			if x + k < 0:
				f = False
		if f:
			s += 1
			d[k].pop()
		d[-k].pop()
print(s)


from collections import defaultdict
n = int(input())
r = defaultdict(int)
ans = 0
for i in range(n):
	x = str(input())
	tt = 0
	for y in x:
		if y == '(':
			tt += 1
		elif y == ')':
			tt -= 1
	now = 0
	can = True
	for y in x:
		if y == '(':
			now += 1
			tt -= 1
		elif y == ')':
			now -= 1
			tt += 1
		if now < 0 and tt > 0:
			can = False
			break
	if not can:
		continue
	if r[-now]:
		ans += 1
		r[-now] -= 1
	else:
		r[now] += 1
print(ans)


from collections import defaultdict
n = int(input())
brackets = []
for _ in range(n):
	bracket = input()
	brackets.append(bracket)
comp = defaultdict(int)
pairs = 0
for bracket in brackets:
	stack = []
	left = 0
	right = 0
	for c in bracket:
		if c == '(':
			stack.append('(')
			left += 1
		elif c == ')' and len(stack) != 0:
			stack.pop()
			left -= 1
		else:
			right += 1
	if left > 0 and right > 0:
		continue
	if comp[left, right] > 0:
		pairs += 1
		comp[left, right] -= 1
	else:
		comp[right, left] += 1
print(pairs)


d = {}
r = 0
for _ in [0] * int(input()):
	m = c = 0
	for x in input():
		if x < ')':
			c += 1
		else:
			c -= 1
			m = min(m, c)
	if c == m == 0:
		r += 1
	elif m in (0, c):
		i = m < 0
		d.setdefault((c, -m)[i], [0, 0])[i] += 1
print(sum(map(min, d.values())) + r // 2)


TN = 1

def checking(a):
	ans = []
	z = 0
	o = 0
	for i in a:
		if i == '(':
			ans.append(i)
		else:
			try:
				ans.pop()
			except:
				z += 1
	o += len(ans)
	return (o, z)

def solution():
	n = int(input())
	l = []
	an = 0
	for i in range(n):
		l.append(list(input()))
	otkr = []
	zakr = []
	for i in range(n):
		(o, z) = checking(l[i])
		if o and (not z):
			otkr.append(o)
		if z and (not o):
			zakr.append(z)
		if o == 0 and z == 0:
			an += 1
	zakr.append(-1)
	otkr.append(0)
	z = max(max(otkr), max(zakr))
	ans1 = [0 for i in range(z + 2)]
	ans2 = [0 for i in range(z + 2)]
	for i in otkr:
		ans1[i] += 1
	for i in zakr:
		ans2[i] += 1
	ans = int(an / 2)
	for i in range(z + 2):
		ans += min(ans1[i], ans2[i])
	print(ans)
while TN != 0:
	solution()
	TN -= 1


def f(input_string):
	s = []
	balanced = True
	index = 0
	left = 0
	while index < len(input_string):
		token = input_string[index]
		if token == '(':
			s.append(token)
		elif token == ')':
			if len(s) == 0:
				balanced = False
				left += 1
			else:
				s.pop()
		index += 1
	return [balanced and len(s) == 0, left, len(s)]
n = int(input())
ini = []
for _ in range(n):
	s = input()
	ini.append(s)
arr = []
count = 0
bal = 0
left = dict()
right = dict()
for i in range(n):
	ret = f(ini[i])
	if ret[0]:
		bal += 1
	else:
		if ret[1] == 0:
			r = ret[2]
			if r in right:
				right[r] += 1
			else:
				right[r] = 1
		if ret[2] == 0:
			r = ret[1]
			if r in left:
				left[r] += 1
			else:
				left[r] = 1
count += bal // 2
if left.keys():
	for i in left.keys():
		if i in right:
			count += min(left[i], right[i])
print(count)


from collections import defaultdict
N = int(input())
l = []
for i in range(N):
	l.append(input())
cnt = defaultdict(int)
res = 0
for string in l:
	st = []
	i = 0
	while i < len(string):
		if not st:
			st.append(string[i])
		elif st[-1] == '(' and string[i] == ')':
			st.pop()
		else:
			st.append(string[i])
		i += 1
	length = len(st)
	if length == 0:
		cnt[0] += 1
	elif '(' in st and ')' in st:
		continue
	elif '(' in st:
		if cnt[-length] != 0:
			cnt[-length] -= 1
			res += 1
		else:
			cnt[length] += 1
	elif cnt[length] != 0:
		cnt[length] -= 1
		res += 1
	else:
		cnt[-length] += 1
res += cnt[0] // 2
print(res)


def isbalanced(s):
	if s == '(' * (len(s) // 2) + ')' * (len(s) // 2):
		return True
	elif s == '()' * (len(s) // 2):
		return True
	else:
		return False
n = int(input())
a = [input() for i in range(n)]
ans = 0
(l, r) = ({}, {})
for i in a:
	(x, y) = (0, 0)
	for j in range(len(i)):
		if i[j] == '(':
			x += 1
		elif x > 0:
			x -= 1
		else:
			y += 1
	if x == 0 and y == 0:
		ans += 1
	elif y == 0:
		if x in l:
			l[x] += 1
		else:
			l[x] = 1
	elif x == 0:
		if y in r:
			r[y] += 1
		else:
			r[y] = 1
cnt = 0
for i in l:
	if i in r:
		cnt += min(l[i], r[i])
print(cnt + ans // 2)


from collections import *
from copy import deepcopy
n = int(input())
items = [input() for i in range(n)]
item_num = defaultdict(int)

def check(exp):
	(s1, s2) = (0, 0)
	for c in exp:
		s1 += c == '('
		s2 -= c == ')' and s1 == 0
		s1 -= c == ')' and s1 != 0
	return False if s1 and s2 else s1 if s1 else s2 if s2 else 0
for item in items:
	val = check(item)
	if val is False:
		continue
	item_num[val] += 1
ans = sum([min(item_num[item], item_num[-1 * item]) for item in deepcopy(item_num)]) // 2
print(ans)


import os
import sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from collections import Counter
import heapq
from collections import Counter
from bisect import bisect_right

def multiples(x):
	ans = 1
	for i in range(2, int(x ** 0.5)):
		var = x
		cnt = 0
		while var % i == 0:
			var = var // i
			cnt += 1
		ans *= cnt + 1
	return ans
n = int(input())
ans = 0
d = {}
dd = {}
for i in range(n):
	s = input()
	cnt = 0
	mi = 10 ** 18
	for i in s:
		if i == '(':
			cnt += 1
		else:
			cnt -= 1
		mi = min(mi, cnt)
	if cnt == 0 and mi == 0:
		if 0 in d:
			d[0] += 1
		else:
			d[0] = 1
	elif cnt < 0 and mi < 0 and (cnt == mi):
		if cnt in dd:
			dd[cnt] += 1
		else:
			dd[cnt] = 1
	elif cnt > 0 and mi >= 0:
		if cnt in d:
			d[cnt] += 1
		else:
			d[cnt] = 1
	else:
		continue
for j in d:
	if j == 0:
		continue
	if -j in dd:
		ans += min(d[j], dd[-j])
if 0 in d:
	ans += d[0] // 2
print(ans)


n = int(input())
ans = []
mask = []
elems = {}
an = 0
for i in range(n):
	(l, r) = (0, 0)
	a = list(input())
	for k in range(len(a)):
		if a[k] == '(':
			r += 1
		elif r == 0:
			l += 1
		else:
			r -= 1
	ans.append((l, r))
	if (l, r) in elems:
		elems[l, r] += 1
	else:
		elems[l, r] = 1
		elems[r, l] = 0
for i in range(n):
	if (ans[i][0] == 0 and ans[i][1] == 0) and elems[ans[i]] > 1:
		an += 1
		elems[ans[i]] -= 2
		continue
	if elems[ans[i]] > 0 and elems[ans[i][1], ans[i][0]] > 0 and (ans[i][0] == 0 or ans[i][1] == 0):
		elems[ans[i]] -= 1
		elems[ans[i][1], ans[i][0]] -= 1
		an += 1
print(an)


import math
import bisect
import itertools
import sys
I = lambda : sys.stdin.readline()
mod = 10 ** 9 + 7

def mindiff(a):
	b = a[:]
	b.sort()
	m = 10000000000
	for i in range(len(b) - 1):
		if b[i + 1] - b[i] < m:
			m = b[i + 1] - b[i]
	return m

def lcm(a, b):
	return a * b // math.gcd(a, b)

def merge(a, b):
	i = 0
	j = 0
	c = 0
	ans = []
	while i < len(a) and j < len(b):
		if a[i] < b[j]:
			ans.append(a[i])
			i += 1
		else:
			ans.append(b[j])
			c += len(a) - i
			j += 1
	ans += a[i:]
	ans += b[j:]
	return (ans, c)

def mergesort(a):
	if len(a) == 1:
		return (a, 0)
	mid = len(a) // 2
	(left, left_inversion) = mergesort(a[:mid])
	(right, right_inversion) = mergesort(a[mid:])
	(m, c) = merge(left, right)
	c += left_inversion + right_inversion
	return (m, c)

def is_prime(num):
	if num == 1:
		return False
	if num == 2:
		return True
	if num == 3:
		return True
	if num % 2 == 0:
		return False
	if num % 3 == 0:
		return False
	t = 5
	a = 2
	while t <= int(math.sqrt(num)):
		if num % t == 0:
			return False
		t += a
		a = 6 - a
	return True

def ceil(a, b):
	if a % b == 0:
		return a // b
	else:
		return a // b + 1

def binsearch(arr, b, low, high):
	if low == high:
		return low
	if arr[math.ceil((low + high) / 2)] < b:
		return binsearch(arr, b, low, math.ceil((low + high) / 2) - 1)
	else:
		return binsearch(arr, b, math.ceil((low + high) / 2), high)

def ncr1(n, r):
	s = 1
	for i in range(min(n - r, r)):
		s *= n - i
		s %= mod
		s *= pow(i + 1, mod - 2, mod)
		s %= mod
	return s

def calc(n, m, r):
	s = 0
	for i in range(0, r + 1, 2):
		s += ncr1(n, i) * ncr1(m, i)
		s %= mod
	return s
d = {}
for j in range(int(input())):
	s = input()
	f = False
	a = []
	o = 0
	c = 0
	a.append(s)
	for i in range(len(s)):
		if s[i] == ')' and o == 0:
			c += 1
		elif s[i] == ')':
			o -= 1
		else:
			o += 1
	d[o, c] = d.get((o, c), 0) + 1
ans = 0
for i in d:
	(x, y) = i
	if d[i]:
		if x == 0 and y != 0:
			if d.get((y, 0), 0) > 0:
				k = min(d[0, y], d[y, 0])
				d[y, 0] -= k
				d[0, y] -= k
				ans += k
		elif y == 0 and x != 0:
			if d.get((0, x), 0) > 0:
				k = min(d[0, x], d[x, 0])
				d[x, 0] -= k
				d[0, x] -= k
				ans += k
		elif x == 0 and y == 0:
			if d.get((0, 0), 0) > 1:
				ans += d[i] // 2
print(ans)


d = {}
r = 0
for _ in [0] * int(input()):
	m = c = 0
	for x in input():
		c += 81 - 2 * ord(x)
		m = min(m, c)
	r += c == m == 0
	d.setdefault((c, -m)[m < 0], [0, 0])[m < 0] += m in (0, c)
print(sum(map(min, d.values())) + r // 2)


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 os import path
import sys, time
from math import ceil, floor, gcd, log, log2, factorial, cos, sin, pi
from collections import defaultdict, Counter, OrderedDict, deque
from string import ascii_lowercase, ascii_uppercase
from bisect import *
from functools import reduce
from operator import mul
maxx = float('inf')
I = lambda : int(sys.stdin.buffer.readline())
tup = lambda : map(int, sys.stdin.buffer.readline().split())
lint = lambda : [int(x) for x in sys.stdin.buffer.readline().split()]
S = lambda : sys.stdin.readline().strip('\n')
grid = lambda r: [lint() for i in range(r)]
stpr = lambda x: sys.stdout.write(f'{x}' + '\n')
star = lambda x: print(' '.join(map(str, x)))
localsys = 0
start_time = time.time()
if path.exists('input.txt'):
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
n = int(input())
(d, A, ans) = (defaultdict(int), [input().rstrip() for _ in range(n)], 0)
for _ in range(n):
	x = A[_]
	(i, N, st) = (0, len(x), [])
	while i < N:
		if st and st[-1] == '(' and (x[i] == ')'):
			st.pop()
		else:
			st.append(x[i])
		i += 1
	if st:
		if len(set(st)) == 1:
			d[tuple(st)] += 1
	else:
		ans += 1
ans //= 2
for i in d:
	if i[0] == '(':
		y = tuple([')'] * len(i))
	else:
		y = tuple(['('] * len(i))
	if y in d:
		ans += min(d[i], d[y])
		d[i] = d[y] = 0
print(ans)
if localsys:
	print('\n\nTime Elased :', time.time() - start_time, 'seconds')


n = int(input())
r = []
l = []
z = []
for i in range(n):
	s = input()
	k1 = 0
	left = False
	right = False
	for i in s:
		if i == ')':
			k1 += 1
		else:
			k1 -= 1
		if k1 > 0:
			left = True
	s = s[::-1]
	k2 = 0
	for i in s:
		if i == ')':
			k2 += 1
		else:
			k2 -= 1
		if k2 < 0:
			right = True
	if not (left and right):
		if left:
			l.append(k1)
		elif right:
			r.append(abs(k2))
		else:
			z.append(0)
k = 0
l.sort()
r.sort()
if len(l) < len(r):
	e = 0
	for i in l:
		if e < len(r):
			while e < len(r) and i > r[e]:
				e += 1
			if e < len(r) and i == r[e]:
				k += 1
				e += 1
else:
	e = 0
	for i in r:
		if e < len(l):
			while e < len(l) and i > l[e]:
				e += 1
			if e < len(l) and i == l[e]:
				k += 1
				e += 1
k += len(z) // 2
print(k)


from collections import *
d = Counter()
for _ in [0] * int(input()):
	m = c = 0
	for x in input():
		c += 1
		if x > '(':
			c -= 2
			m = min(m, c)
	d[c] += m in (0, c)
print(sum((min(d[k], d[-k]) for k in d)) // 2)


def check_para(v):
	c = 0
	m = 0
	for i in v:
		if i == ')':
			c -= 1
		else:
			c += 1
		m = min(m, c)
	if m < 0 and m < c:
		return None
	else:
		return c
n = int(input())
s = []
for i in range(n):
	v = input()
	v = check_para(v)
	if v is not None:
		s.append(v)
d = {}
out = 0
for i in s:
	if d.get(-i, 0):
		d[-i] -= 1
		out += 1
	else:
		d[i] = d.get(i, 0) + 1
print(out)


def simplify(seq):
	num_open = 0
	num_close = 0
	for bracket in seq:
		if bracket == '(':
			num_open += 1
		elif bracket == ')' and num_open > 0:
			num_open -= 1
		elif bracket == ')' and num_open <= 0:
			num_close += 1
	if num_open > 0 and num_close > 0:
		return None
	elif num_open == 0:
		return -num_close
	else:
		return num_open
n = int(input())
brackets = {}
brackets[0] = 0
for i in range(n):
	seq = simplify(input().strip())
	if seq is not None:
		if seq in brackets.keys():
			brackets[seq] += 1
		else:
			brackets[seq] = 1
answer = brackets[0] // 2
for k in brackets.keys():
	if k > 0 and -k in brackets.keys():
		answer += min(brackets[k], brackets[-k])
print(answer)


n = int(input())
lparen = []
rparen = []
bparen = 0
for i in range(n):
	p = input()
	right = 0
	left = 0
	for j in range(len(p)):
		if p[j] == '(':
			right += 1
		elif right == 0:
			left += 1
		else:
			right -= 1
	if right == 0 and left == 0:
		bparen += 1
	elif right == 0:
		lparen.append(left)
	elif left == 0:
		rparen.append(right)
num = int(bparen / 2)
lparen.sort()
rparen.sort()
l = 0
r = 0
while l < len(lparen) and r < len(rparen):
	if lparen[l] == rparen[r]:
		num += 1
		l += 1
		r += 1
	elif lparen[l] > rparen[r]:
		r += 1
	else:
		l += 1
print(num)


n = int(input())
d1 = {}
d2 = {}
cc = 0
for i in range(n):
	s = input()
	(open, left) = (0, 0)
	for i in s:
		if i == ')':
			if open > 0:
				open -= 1
			else:
				left += 1
		else:
			open += 1
	if open > 0 and left > 0:
		continue
	elif open == 0 and left == 0:
		cc += 1
	elif open > 0:
		d1[open] = 1 if open not in d1 else d1[open] + 1
	else:
		closed = left
		d2[closed] = 1 if closed not in d2 else d2[closed] + 1
ans = cc // 2
for each in d1:
	if each not in d2:
		continue
	ans += min(d1[each], d2[each])
print(ans)


def check(s):
	f = 0
	for i in s:
		if i == '(':
			f += 2
		f -= 1
		if f < 0:
			return 0
	return 1

def check2(s):
	f = 0
	for i in s:
		if i == '(':
			f += 2
		f -= 1
		if f > 0:
			return 0
	return 1
n = int(input())
a = {}
b = {}
c = 0
for i in range(n):
	s = input()
	if check(s) or check2(s[::-1]):
		x = s.count('(') - s.count(')')
		if x < 0:
			if x in b:
				b[x] += 1
			else:
				b[x] = 1
		elif x > 0:
			if x in a:
				a[x] += 1
			else:
				a[x] = 1
		else:
			c += 1
f = c // 2
for i in list(a):
	if -i in b:
		f += min(a.get(i), b.get(-i))
print(f)


n = int(input())

def open(s):
	st = []
	n = len(s)
	for i in range(n):
		if s[i] == '(':
			st.append(s[i])
		if s[i] == ')':
			if len(st) == 0:
				st.append(')')
			elif st[-1] == '(':
				st.pop()
			else:
				st.append(')')
	S = ''
	for i in st:
		S += i
	return S
d = {}
r = 0
a = []
for i in range(n):
	S = input()
	b = open(S)
	if b == '':
		r += 1
	else:
		c1 = 0
		c2 = 0
		for j in b:
			if j == ')':
				c1 += 1
			else:
				c2 += 1
		a.append((c1, c2))
		d[c1, c2] = 0
		d[c2, c1] = 0
for i in a:
	d[i] += 1
res = r // 2
for i in a:
	if i[0] > 0 and i[1] > 0:
		continue
	if d[i[:2][::-1]] > 0 and d[i[:2]] > 0:
		d[i[:2][::-1]] -= 1
		d[i[:2]] -= 1
		res += 1
print(res)


def binSearch(arr, value, key=lambda x: x):
	(l, h) = (0, len(arr) - 1)
	while l <= h:
		x = (h + l) // 2
		k = key(arr[x])
		if value < k:
			h = x - 1
		elif value > k:
			l = x + 1
		else:
			return x
	return -1

def seq_repr(brcs):
	seq = []
	for i in brcs:
		if len(seq) != 0 and seq[-1] == '(' and (i == ')'):
			seq.pop(-1)
		else:
			seq.append(i)
	(a, b) = (0, 0)
	ln = len(seq)
	(i, j) = (0, ln - 1)
	while i < ln and seq[i] == ')':
		a += 1
		i += 1
	while j >= 0 and seq[j] == '(':
		b += 1
		j -= 1
	return (a, b)
n = int(input())
cnt = 0
(seq1, seq2) = ([], [])
for _ in range(n):
	(a, b) = seq_repr(list(input()))
	if a == 0 and b == 0:
		cnt += 1
	elif a == 0 and b != 0:
		seq1.append(b)
	elif a != 0 and b == 0:
		seq2.append(a)
cnt //= 2
seq2.sort()
for k in seq1:
	idx = binSearch(seq2, k)
	if idx != -1:
		cnt += 1
		seq2.pop(idx)
print(cnt)


(r, l, m) = ([], {}, 0)
for k in range(int(input())):
	s = input()
	(lb, rb, a, b) = (0, 0, 0, 0)
	for i in range(len(s)):
		if s[i] == '(':
			rb += 1
		else:
			rb -= 1
		if s[-1 - i] == ')':
			lb += 1
		else:
			lb -= 1
		if rb < 0:
			a = 1
		if lb < 0:
			b = 1
		if a and b:
			break
	else:
		if rb > 0:
			r.append(rb)
		elif rb < 0:
			l[lb] = l.get(lb, 0) + 1
		else:
			m += 1
m //= 2
for i in r:
	if i in l.keys() and l[i]:
		m += 1
		l[i] -= 1
print(m)


import sys, os, io

def rs():
	return sys.stdin.readline().rstrip()

def ri():
	return int(sys.stdin.readline())

def ria():
	return list(map(int, sys.stdin.readline().split()))

def ws(s):
	sys.stdout.write(s + '\n')

def wi(n):
	sys.stdout.write(str(n) + '\n')

def wia(a):
	sys.stdout.write(' '.join([str(x) for x in a]) + '\n')
import math, datetime, functools, itertools, operator, bisect, fractions
from collections import deque, defaultdict, OrderedDict, Counter
from fractions import Fraction
from decimal import Decimal

def main():
	starttime = datetime.datetime.now()
	if os.path.exists('input.txt'):
		sys.stdin = open('input.txt', 'r')
		sys.stdout = open('output.txt', 'w')
	for i in range(1):
		n = ri()
		d = {}
		for i in range(n):
			s = rs()
			depth = 0
			temp = 0
			for j in s:
				if j == '(':
					depth += 1
				else:
					depth -= 1
				temp = min(temp, depth)
			if temp >= min(0, depth):
				if depth not in d:
					d[depth] = 1
				else:
					d[depth] += 1
		ans = 0
		for i in d:
			if i > 0:
				if -i in d:
					ans += min(d[i], d[-i])
			if i == 0:
				ans += d[i] // 2
		print(ans)
	endtime = datetime.datetime.now()
	time = (endtime - starttime).total_seconds() * 1000
	if os.path.exists('input.txt'):
		print('Time:', time, 'ms')

class FastReader(io.IOBase):
	newlines = 0

	def __init__(self, fd, chunk_size=1024 * 8):
		self._fd = fd
		self._chunk_size = chunk_size
		self.buffer = io.BytesIO()

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self, size=-1):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, self._chunk_size if size == -1 else size))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

class FastWriter(io.IOBase):

	def __init__(self, fd):
		self._fd = fd
		self.buffer = io.BytesIO()
		self.write = self.buffer.write

	def flush(self):
		os.write(self._fd, self.buffer.getvalue())
		(self.buffer.truncate(0), self.buffer.seek(0))

class FastStdin(io.IOBase):

	def __init__(self, fd=0):
		self.buffer = FastReader(fd)
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')

class FastStdout(io.IOBase):

	def __init__(self, fd=1):
		self.buffer = FastWriter(fd)
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.flush = self.buffer.flush
sys.stdin = FastStdin()
sys.stdout = FastStdout()
main()


Y = lambda : int(input())
n = Y()
d = {}
answer = 0
d2 = {}
sts = []
copy = 0
for i in range(n):
	s = input()
	stack = []
	for j in s:
		if len(stack) == 0:
			stack.append(j)
		elif stack[-1] == '(' and stack[-1] != j:
			stack.pop()
		else:
			stack.append(j)
	open_ = stack.count('(')
	close = stack.count(')')
	if open_ == close == 0:
		copy += 1
	elif open_ == 0:
		r = d2.get(close, 0)
		if r:
			answer += 1
			d2[close] -= 1
		else:
			d[close] = d.get(close, 0) + 1
	elif close == 0:
		r = d.get(open_, 0)
		if r:
			answer += 1
			d[open_] -= 1
		else:
			d2[open_] = d2.get(open_, 0) + 1
	else:
		continue
print(answer + copy // 2)


d = {0: [0, 0]}
for _ in [0] * int(input()):
	m = c = 0
	for x in input():
		c += 2 * (x < ')') - 1
		m = min(m, c)
	d.setdefault(abs(c), [0, 0])[m < 0] += m in (0, c)
print(sum(map(min, d.values())) + d[0][0] // 2)


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

def judge(a):
	c0 = a.count('(')
	c1 = a.count(')')
	(ct0, ct1) = (0, 0)
	if c1 > c0:
		ct0 = c1 - c0
	for c in a:
		if c == '(':
			ct0 = ct0 + 1
		if c == ')':
			ct1 = ct1 + 1
		if ct0 < ct1:
			return (False, ct1 - ct0)
			break
	else:
		return (True, c1 - c0)
mp = dict()
for i in s:
	(bo, num) = judge(i)
	if bo:
		if num not in mp:
			mp[num] = 1
		else:
			mp[num] = mp[num] + 1
ans = 0
for i in mp:
	if i < 0 and -i in mp:
		ans = ans + min(mp[i], mp[-i])
	if i == 0:
		ans = ans + mp[i] // 2
print(ans)


from sys import stdin, stdout
from math import gcd, sqrt
from collections import deque
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(x)
hg = lambda x, y: (y + x - 1) // x * x
pw = lambda x: 1 if x == 1 else 1 + pw(x // 2)
chk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False
N = 5 * 10 ** 5 + 7

def br(s, c):
	cnt = ans = 0
	for i in s:
		if i == c:
			cnt += 1
		else:
			cnt -= 1
		if cnt > 0:
			ans += cnt
			cnt = 0
	return ans
left = [0] * N
right = [0] * N
ans = res = 0
for i in range(I()):
	s = S()
	lef = br(s, ')')
	rig = br(s[::-1], '(')
	if lef and rig:
		continue
	elif not lef and (not rig):
		res += 1
	elif lef:
		left[lef] += 1
	else:
		right[rig] += 1
for i in range(N):
	ans += min(left[i], right[i])
print(ans + res // 2)


n = int(input())
d = [0] * (10 ** 6 + 1)
c = 10 ** 5 * 5
for i in range(n):
	s = input()
	k = 0
	mk = 0
	for j in s:
		if j == '(':
			k += 1
		else:
			k -= 1
		if k < 0:
			mk = min(mk, k)
	if mk == k or mk == 0:
		d[k + c] += 1
	else:
		n -= 1
ans = 0
for i in range(c):
	if d[i] != 0:
		ans += min(d[i], d[c * 2 - i])
ans += d[c] // 2
print(ans)


from collections import Counter
n = int(input())
s = Counter()
p = 0
for i in range(n):
	str = input()
	cur = 0
	min = 0
	for j in range(len(str)):
		if str[j] == '(':
			cur += 1
		else:
			cur -= 1
			if cur < min:
				min = cur
	if cur < 0 and min < cur or (cur >= 0 and min < 0) or (cur < 0 and str[len(str) - 1] != ')'):
		continue
	if s[-1 * cur] > 0:
		p += 1
		s[-1 * cur] -= 1
	else:
		s[cur] += 1
print(p)


import collections
n = int(input())

def count(s):
	res = 0
	negRes = 0
	wasNeg = False
	for c in s:
		if c == '(':
			res += 1
		else:
			res -= 1
		if res < 0:
			wasNeg = True
			negRes += res
			res = 0
	if wasNeg and res > 0:
		return None
	return res + negRes
ct = collections.Counter()
res = 0
for i in range(n):
	s = input()
	c = count(s)
	if c is None:
		continue
	if ct[-c] > 0:
		ct[-c] -= 1
		res += 1
	else:
		ct[c] += 1
print(res)


def balance(s):
	ans = 0
	minans = 0
	for i in s:
		if i == '(':
			ans += 1
		if i == ')':
			ans -= 1
		if ans < minans:
			minans = ans
	return (minans, ans - minans)
n = int(input())
a = dict()
for i in range(n):
	x = input()
	b = balance(x)
	if b[0] != 0 and b[1] != 0:
		continue
	b = b[0] + b[1]
	if a.get(b):
		a[b] += 1
	else:
		a[b] = 1
count = 0
for i in list(a.keys()):
	if i > 0 and a.get(-i) and a.get(i):
		m = min(a[i], a[-i])
		count += m
	if i == 0:
		count += a[i] // 2
print(count)


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()


def check(s, reverse):
	if not reverse:
		a = '('
		b = ')'
	else:
		a = ')'
		b = '('
	m = 0
	for c in s:
		if m:
			if c == a:
				m += 1
			else:
				m -= 1
		elif c == b:
			return (False, 0)
		else:
			m += 1
	if not reverse:
		return (True, m)
	else:
		return (True, -m)
n = int(input())
l = []
l0 = 0
for i in range(0, n):
	s = input()
	(b, m) = check(s, False)
	if b == True and m == 0:
		l0 += 1
		continue
	if b == True:
		l.append(m)
		continue
	(b, m) = check(s[::-1], True)
	if b == True:
		l.append(m)
		continue
num = l0 // 2
d = {}
for i in l:
	d[i] = d.get(i, 0) + 1
for i in l:
	if d.get(i) and d.get(-i):
		d[i] -= 1
		d[-i] -= 1
		num += 1
print(num)


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
		elif 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)


n = int(input())
tot = []
for i in range(n):
	a = input()
	summa = 0
	g = 1
	for item in a:
		if summa < 0:
			g = 0
		if item == '(':
			summa += 1
		else:
			summa -= 1
	if summa >= 0:
		if g == 1:
			tot.append(summa)
	elif summa < 0:
		f = summa
		l = 0
		for m in a:
			if f > 0:
				l = 1
			if m == ')':
				f += 1
			else:
				f -= 1
		if l == 0:
			if a[-1] != '(':
				tot.append(summa)
dic = {}
total = 0
for item in tot:
	if item == 0:
		dic[0] = 0
	else:
		dic[abs(item)] = [0, 0]
for item in tot:
	if item > 0:
		dic[item][1] += 1
	elif item == 0:
		dic[item] += 1
	else:
		dic[abs(item)][0] += 1
for item in dic:
	if item != 0:
		total += min(dic[item])
	else:
		total += dic[item] // 2
print(total)


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 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))


import sys
n = int(input())
a = {}
b = {}
thik = 0
for i in range(0, n):
	x = input()
	bal = 0
	gettis = 0
	for c in x:
		if c == '(':
			bal += 1
		elif c == ')':
			if bal:
				bal -= 1
			else:
				gettis += 1
	if gettis > 0 and bal > 0:
		continue
	if gettis == 0 and bal == 0:
		thik += 1
	a.setdefault(bal, 0)
	a[bal] += 1
	b.setdefault(gettis, 0)
	b[gettis] += 1
ans = 0
ans += thik // 2
for i in range(1, 500000):
	ans = ans + min(a.get(i, 0), b.get(i, 0))
print(ans)
sys.exit()


from sys import stdin, stdout
from math import gcd, ceil, sqrt
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
mod = 1000000007
n = ii1()
open_missing = [0] * 500001
close_missing = [0] * 500001
complete = 0
for _ in range(n):
	s = is1()
	stack = []
	for i in s:
		if i == '(':
			stack.append(i)
		if i == ')':
			if len(stack) and stack[-1] == '(':
				stack.pop()
			else:
				stack.append(i)
	if not len(stack):
		complete += 1
	elif stack[0] == ')' and stack[-1] != '(':
		open_missing[len(stack)] += 1
	elif stack[0] == '(' and stack[-1] != ')':
		close_missing[len(stack)] += 1
res = 0
for i in range(len(open_missing)):
	res += min(open_missing[i], close_missing[i])
res += complete // 2
print(res)


n = int(input())
starts = []
ends = []
fulls = 0
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)
	if count > 0:
		if mn == 0:
			starts.append(count)
	elif count < 0:
		if mn == count:
			ends.append(-1 * count)
	elif 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)


import math
n = input()
cases = []
for c in range(int(n)):
	case = input()
	left_extra = 0
	right_extra = 0
	for ii in range(len(case)):
		i = case[ii]
		if i == '(':
			left_extra += 1
		elif i == ')' and left_extra > 0:
			left_extra -= 1
		else:
			right_extra += 1
	if left_extra == 0 or right_extra == 0:
		cases.append([left_extra, right_extra])
total = 0
num = cases.count([0, 0])
if num > 0:
	total += num // 2
cases = list(filter([0, 0].__ne__, cases))
first = {}
second = {}
for case in cases:
	if case[0] == 0:
		if str(case[1]) in first:
			first[str(case[1])] += 1
		else:
			first[str(case[1])] = 1
	elif str(case[0]) in second:
		second[str(case[0])] += 1
	else:
		second[str(case[0])] = 1
for key in first:
	if key in second.keys():
		total += min(int(first[key]), int(second[key]))
print(total)


def legelSeq(seq):
	left = 0
	right = 0
	for chars in seq:
		if chars == '(':
			left += 1
		elif chars == ')':
			if left > 0:
				left -= 1
			else:
				right += 1
	return [left, right]
num = int(input())
sum = 0
seqs = {}
for _ in range(num):
	seq = input()
	seqNum = 0
	temp = []
	flag = False
	judge = legelSeq(seq)
	if judge[0] > 0 and judge[1] > 0:
		continue
	elif judge[0] > 0:
		if -judge[0] in seqs and seqs[-judge[0]] > 0:
			seqs[-judge[0]] -= 1
			sum += 1
		elif judge[0] in seqs:
			seqs[judge[0]] += 1
		else:
			seqs[judge[0]] = 1
	elif judge[1] in seqs and seqs[judge[1]] > 0:
		seqs[judge[1]] -= 1
		sum += 1
	elif -judge[1] in seqs:
		seqs[-judge[1]] += 1
	else:
		seqs[-judge[1]] = 1
print(sum)


from sys import stdin

def calculate_score(bracket):
	score = dict()
	for element in bracket:
		count = 0
		for c in element:
			if c == '(':
				count += 1
			else:
				count -= 1
		score[element] = count
	return score

def is_positive(string):
	count = 0
	for c in string:
		if c == '(':
			count += 1
		else:
			count -= 1
		if count < 0:
			return False
	if count < 0:
		return False
	return True

def is_negative(string):
	count = 0
	for i in range(len(string) - 1, -1, -1):
		if string[i] == '(':
			count += 1
		else:
			count -= 1
		if count > 0:
			return False
	return True
n = int(stdin.readline().strip())
opening = dict()
closing = dict()
bracket = []
for _ in range(n):
	bracket.append(stdin.readline().strip())
score = calculate_score(bracket)
zero = 0
for element in bracket:
	if is_positive(element):
		if score[element] == 0:
			zero += 1
			continue
		else:
			try:
				opening[score[element]] += 1
			except:
				opening[score[element]] = 1
		continue
	elif is_negative(element):
		try:
			closing[score[element]] += 1
		except:
			closing[score[element]] = 1
		continue
count = zero // 2
for key in opening:
	if -key in closing:
		count += min(opening[key], closing[-key])
print(count)


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)


def count():
	x = input()
	c = 0
	k = 0
	for i in x:
		if i == '(':
			c += 1
		if i == ')':
			if c > 0:
				c -= 1
			else:
				k += 1
	if c == 0 and k > 0:
		return -k
	elif c >= 0 and k == 0:
		return c
	else:
		return None
n = int(input())
c = {}
a = 0
for i in range(n):
	ans = count()
	if ans != None:
		if c.get(-ans) != None and c[-ans] > 0:
			a += 1
			c[-ans] -= 1
		elif c.get(ans) != None:
			c[ans] += 1
		else:
			c[ans] = 1
print(a)


def mi():
	return map(int, input().split())
l = [0] * (10 ** 5 * 5 + 5)
r = [0] * (10 ** 5 * 5 + 5)
try:
	n = int(input())
	for _ in range(n):
		a = input()
		la = len(a)
		s = 0
		f = 0
		for i in a:
			if i == '(':
				if s < 0:
					f = 1
					break
				s += 1
			else:
				s -= 1
		if f == 0 and s >= 0:
			r[s] += 1
		s = 0
		f = 0
		a = a[::-1]
		for i in a:
			if i == ')':
				s += 1
			else:
				if s <= 0:
					f = 1
					break
				s -= 1
		if f == 0 and s > 0:
			l[s] += 1
	ans = r[0] // 2
	for i in range(1, 500000 + 5):
		ans += min(l[i], r[i])
	print(ans)
except EOFError:
	print(0)


def hallar_abres_cierras(a, abre, cierra, lista):
	if a[0] == ')' and a[-1] == '(':
		pass
	else:
		aux = 0
		for h in range(len(a)):
			if a[h] == '(':
				aux += 1
			else:
				aux -= 1
			if aux < 0:
				abre += 1
				aux = 0
		cierra = aux
		if abre != 0 and cierra != 0:
			pass
		elif abre == 0 and cierra != 0:
			lista.append(cierra)
		else:
			lista.append(abre * -1)
i = int(input())
lista = []
for j in range(i):
	a = str(input())
	abre = 0
	cierra = 0
	hallar_abres_cierras(a, abre, cierra, lista)
cantidad = 0
j = 1
if lista == []:
	pass
else:
	maximo = max(lista)
	cantidad += lista.count(0) // 2
	while j <= maximo:
		cantidad_pos = lista.count(j)
		cantidad_neg = lista.count(j * -1)
		cantidad += min(cantidad_pos, cantidad_neg)
		j += 1
print(cantidad)


n = int(input())
(lss, rss, oss) = (dict(), dict(), 0)
for _ in range(0, n):
	s = input()
	l = len(s)
	(minn, maxx, cur) = (0, 0, 0)
	for i in range(0, l, 1):
		cur += {'(': 1, ')': -1}[s[i]]
		minn = min(minn, cur)
	cur = 0
	for i in range(l - 1, -1, -1):
		cur += {'(': 1, ')': -1}[s[i]]
		maxx = max(maxx, cur)
	if minn != 0 and maxx != 0:
		continue
	elif minn != 0 and maxx == 0:
		if -minn not in lss:
			lss[-minn] = 0
		lss[-minn] += 1
	elif minn == 0 and maxx != 0:
		if maxx not in rss:
			rss[maxx] = 0
		rss[maxx] += 1
	else:
		oss += 1
res = oss // 2
for i in lss:
	if i in rss:
		res += min(lss[i], rss[i])
print(res)


n = int(input())
a = []
for _ in range(n):
	i = input()
	(o, c) = (i.count('('), i.count(')'))
	bal = 0
	for j in i:
		if j == '(':
			bal += 1
		elif bal:
			bal -= 1
			o -= 1
			c -= 1
	if o and c:
		continue
	a.append(o - c)
a.sort()
(i, j) = (0, len(a) - 1)
ans = 0
while i < j:
	if a[i] + a[j] == 0:
		ans += 1
		i += 1
		j -= 1
	elif a[i] + a[j] > 0:
		j -= 1
	else:
		i += 1
print(ans)


n = int(input())

def check(str):
	count = 0
	nc = 0
	flag = 0
	mn = 1
	for i in str:
		if i == '(':
			count += 1
			if flag:
				nc += 1
		elif i == ')':
			count -= 1
			if flag:
				nc -= 1
		if count < 0:
			flag = 1
			if count < mn:
				mn = count
				nc = 0
	return None if flag and nc > 0 else count if flag == 0 else mn
todo = {}
ans = 0
for _ in range(n):
	inp = check(input())
	if inp is None:
		continue
	elif todo.get(-inp, 0) > 0:
		ans += 1
		todo[-inp] -= 1
	else:
		todo[inp] = todo.get(inp, 0) + 1
print(ans)


n = int(input())
m1 = []
m = []
value = 0
test = 0
for i in range(n):
	test1 = 0
	value = 0
	a = list(input())
	test = 0
	for j in a:
		if j == '(':
			value += 1
			test += 1
		else:
			value -= 1
			if test > 0:
				test -= 1
		test1 = min(value, test1)
	if test == value:
		m1.append(value)
	if test1 == value and value < 0:
		m.append(value)
otvet = 0
j = 0
for i in range(len(m1)):
	if -m1[i] in m:
		otvet += 1
		m.pop(m.index(-m1[i]))
print(otvet + m1.count(0) // 2)


def GetLeftRightBrackets(seq):
	stack = []
	right = 0
	for i in seq:
		if i == '(':
			stack.append(1)
		elif stack == []:
			right += 1
		else:
			stack.pop()
	left = len(stack)
	return (left, right)

def IsCorrect(seq):
	stack = []
	for i in seq:
		if i == '(':
			stack.append(1)
		elif stack == []:
			return False
		else:
			stack.pop()
	if stack == []:
		return True
	return False

def Parenthisis(seqs):
	counts_left = {}
	counts_right = {}
	correct = 0
	for seq in seqs:
		if IsCorrect(seq):
			correct += 1
			continue
		(left, right) = GetLeftRightBrackets(seq)
		if left != 0 and right == 0:
			if left not in counts_left.keys():
				counts_left[left] = 1
			else:
				counts_left[left] += 1
		elif right != 0 and left == 0:
			if right not in counts_right.keys():
				counts_right[right] = 1
			else:
				counts_right[right] += 1
	pairs = 0
	for i in counts_left.keys():
		if i in counts_right.keys():
			if counts_right[i] >= 1:
				m = min(counts_left[i], counts_right[i])
				counts_left[i] -= m
				counts_right[i] -= m
				pairs += m
	return pairs + correct // 2

def main():
	n = int(input())
	seqs = []
	for i in range(n):
		seqs.append(input())
	print(Parenthisis(seqs))
main()


from collections import deque

def f(a):
	q = deque()
	for i in a:
		if i == '(':
			q.append(i)
		elif len(q) == 0:
			q.append(i)
		elif q[-1] == '(':
			q.pop()
		else:
			q.append(i)
	l = q.count('(')
	r = q.count(')')
	if l == 0 and r != 0:
		ans = -r
	elif l != 0 and r == 0:
		ans = l
	elif l == 0 and r == 0:
		ans = 0
	elif l > 0 and r > 0:
		ans = 10000000
	return ans
n = int(input())
b = []
for i in range(n):
	a = input()
	b.append(f(a))
b.sort()
ans = 0
i = 0
j = len(b) - 1
while i < j:
	if abs(b[i]) == abs(b[j]) and b[i] + b[j] == 0:
		ans += 1
		i += 1
		j -= 1
	elif abs(b[i]) > abs(b[j]) and b[i] < 0 and (b[j] > 0):
		i += 1
	elif abs(b[i]) < abs(b[j]) and b[i] < 0 and (b[j] > 0):
		j -= 1
	elif b[i] == 0 and b[j] > 0:
		j -= 1
	elif b[i] < 0 and b[j] == 0:
		i += 1
	elif b[i] * b[j] >= 0:
		break
print(ans)


from sys import stdin
MID_MAX_INDEX = 510000
n = int(stdin.readline())
seqList = [0] * (2 * MID_MAX_INDEX)
for i in range(n):
	seq = stdin.readline()
	lc = 0
	mb = 0
	for symb in seq:
		if symb == '(':
			lc += 1
		elif symb == ')':
			lc -= 1
			if mb > lc:
				mb = lc
	if mb != min(lc, 0):
		continue
	seqList[lc + MID_MAX_INDEX] += 1
count = seqList[MID_MAX_INDEX] // 2
for i in range(1, MID_MAX_INDEX):
	count += min(seqList[MID_MAX_INDEX - i], seqList[MID_MAX_INDEX + i])
print(count)


def answer(n, A):
	dopen = {}
	dclose = {}
	count = 0
	for i in range(n):
		s = [A[i][0]]
		for j in range(1, len(A[i])):
			if A[i][j] == ')':
				if s and s[-1] == '(':
					s.pop()
				else:
					s.append(')')
			else:
				s.append('(')
		if len(s) == 0:
			count += 1
		else:
			c = 0
			for i in s:
				if i == ')':
					c += 1
			o = len(s) - c
			if c == 0:
				if o in dopen:
					dopen[o] += 1
				else:
					dopen[o] = 1
			elif o == 0:
				if c in dclose:
					dclose[c] += 1
				else:
					dclose[c] = 1
	ans = count // 2
	for key in dopen:
		if key in dclose:
			ans += min(dopen[key], dclose[key])
	return ans
n = int(input())
arr = []
for i in range(n):
	arr.append(input())
print(answer(n, arr))


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
		elif 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
		elif L.get(cnt, 0) > 0:
			ans += 1
			L[cnt] -= 1
		else:
			R[cnt] = R.get(cnt, 0) + 1
print(ans)


import sys

def input():
	return sys.stdin.readline().strip()
from collections import deque, Counter
N = int(input())
cnt = {'l': Counter(), 'r': Counter(), 'lr': 0}
for _ in range(N):
	l = r = 0
	for c in input():
		if c == '(':
			l += 1
		elif l != 0:
			l -= 1
		else:
			r += 1
	if l == 0 and r == 0:
		cnt['lr'] += 1
	elif l == 0:
		cnt['r'][r] += 1
	elif r == 0:
		cnt['l'][l] += 1
ans = 0
for (k, v) in cnt['l'].items():
	ans += min(v, cnt['r'][k])
ans += cnt['lr'] // 2
print(ans)


n = int(input())
parens = [0 for x in range(n)]
for i in range(n):
	parens[i] = input()
left_dict = {}
right_dict = {}
max_left = 0
max_right = 0
for i in range(n):
	left = True
	right = True
	current = parens[i]
	m = len(current)
	left_count = 0
	for j in range(m):
		if current[j] == '(':
			left_count += 1
		else:
			left_count -= 1
		if left_count < 0:
			left = False
			break
	if left:
		left_dict[left_count] = left_dict.get(left_count, 0) + 1
		max_left = max(max_left, left_count)
	right_count = 0
	for j in range(m):
		j = m - 1 - j
		if current[j] == ')':
			right_count += 1
		else:
			right_count -= 1
		if right_count < 0:
			right = False
			break
	if right:
		right_dict[right_count] = right_dict.get(right_count, 0) + 1
		max_right = max(max_right, right_count)
sum = left_dict.get(0, 0) // 2
MAX_VALUE = min(max_left, max_right) + 1
for i in range(1, MAX_VALUE):
	sum += min(left_dict.get(i, 0), right_dict.get(i, 0))
print(sum)


import sys

def ball(s):
	left = right = 0
	for i in s:
		if i is ')':
			if left:
				left -= 1
			else:
				right += 1
		else:
			left += 1
	return (left, right)
n = int(input())
ans = zero = 0
(ld, rd) = ({}, {})
for i in range(n):
	s = sys.stdin.readline().strip()
	(left, right) = ball(s)
	if left != 0 and right != 0:
		continue
	elif left:
		if rd.get(left, False):
			rd[left] -= 1
			ans += 1
		else:
			ld[left] = ld.get(left, 0) + 1
	elif right:
		if ld.get(right, False):
			ld[right] -= 1
			ans += 1
		else:
			rd[right] = rd.get(right, 0) + 1
	else:
		zero += 1
print(zero // 2 + ans)


n = int(input())
arr = []
yy = 0
ss = set()
for ii in range(n):
	s = input()
	stack = []
	xx = 0
	for i in range(len(s)):
		if s[i] == '(':
			stack.append(s[i])
			continue
		if s[i] == ')':
			if len(stack) == 0:
				stack.append(s[i])
				continue
			if stack[-1] == '(':
				stack.pop()
				continue
			else:
				stack.append(s[i])
	if len(stack) == 0:
		yy += 1
		continue
	ca = 0
	cb = 0
	for i in stack:
		if i == '(':
			ca += 1
		if i == ')':
			cb += 1
	if ca > 0 and cb > 0:
		continue
	ss.add(len(stack))
	if stack[-1] == ')':
		arr.append(-1 * len(stack))
	else:
		arr.append(len(stack))
ans = yy // 2
d = {}
for i in arr:
	if i in d:
		d[i] += 1
	else:
		d[i] = 1
for i in ss:
	x = i
	y = i * -1
	x1 = 0
	y1 = 0
	if x in d:
		x1 += d[x]
	if y in d:
		y1 += d[y]
	ans += min(x1, y1)
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)


n = int(input())
d = {}
for i in range(n):
	s = input()
	b = []
	for c in s:
		if c == '(':
			b.append(c)
		elif not b == [] and b[-1] == '(':
			b.pop()
		else:
			b.append(c)
	count1 = 0
	count2 = 0
	for c in b:
		if c == ')':
			count1 += 1
		else:
			count2 += 1
	if count1 >= 0 and count2 == 0:
		try:
			d[count1] = (d[count1][0] + 1, d[count1][1])
		except:
			d[count1] = (1, 0)
	elif count1 == 0 and count2 > 0:
		try:
			d[count2] = (d[count2][0], d[count2][1] + 1)
		except:
			d[count2] = (0, 1)
try:
	ans = d[0][0] // 2
except:
	ans = 0
for c in d:
	ans += min(d[c][0], d[c][1])
print(ans)


II = lambda : int(input())

def check(bs):
	cnt = 0
	for b in bs:
		if b == '(':
			cnt += 1
		else:
			cnt -= 1
	ccnt = 0
	if cnt >= 0:
		for b in bs:
			if b == '(':
				ccnt += 1
			else:
				ccnt -= 1
			if ccnt < 0:
				return None
	else:
		for b in bs[::-1]:
			if b == ')':
				ccnt += 1
			else:
				ccnt -= 1
			if ccnt < 0:
				return None
	return cnt

def main():
	N = II()
	(bc_plus, bc_minus, bc_zero) = ([], [], [])
	for _ in range(N):
		cnt = check(input().strip())
		if cnt is None:
			continue
		if cnt < 0:
			bc_minus.append(-cnt)
		elif cnt == 0:
			bc_zero.append(cnt)
		else:
			bc_plus.append(cnt)
	ans = len(bc_zero) // 2
	bc_minus.sort()
	bc_plus.sort()
	(i, j) = (0, 0)
	while i < len(bc_minus) and j < len(bc_plus):
		if bc_minus[i] == bc_plus[j]:
			ans += 1
			i += 1
			j += 1
		elif bc_minus[i] < bc_plus[j]:
			i += 1
		else:
			j += 1
	return ans
print(main())


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 left.items():
	try:
		Ans += min(right[key], value)
	except:
		pass
print(Ans)


def counter(bracket):
	left = 0
	right = 0
	stack = []
	for i in bracket:
		if i == '(':
			stack.append(i)
		elif stack:
			stack.pop()
		else:
			right += 1
	left += len(stack)
	return (left, right)
n = int(input())
match = {}
for _ in range(n):
	now = input()
	count = counter(now)
	if count in match:
		match[count] += 1
	else:
		match[count] = 1
total = 0
for i in match:
	if i[::-1] in match:
		if i == (0, 0):
			total += match[i] // 2
		if i[0] == 0 and i[1] != 0 or (i[1] == 0 and i[0] != 0):
			total += min(match[i], match[i[::-1]])
		match[i] = 0
		match[i[::-1]] = 0
print(total)


from collections import defaultdict
n = int(input())
cnt = defaultdict(int)
ans = 0
for _ in range(n):
	s = input()
	(l, r) = (0, 0)
	for si in s:
		if si == '(':
			l += 1
		elif l > 0:
			l -= 1
		else:
			r += 1
	if l > 0 and r > 0:
		continue
	key = r if r > 0 else -l
	if cnt[-key] > 0:
		ans += 1
		cnt[-key] -= 1
	else:
		cnt[key] += 1
print(ans)


import os, sys
from io import BytesIO, IOBase
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
from math import ceil
mod = 10 ** 9 + 7
for _ in range(1):
	n = int(input())
	p = {}
	l = len
	for i in range(n):
		s = []
		(a, b) = (0, 0)
		z = input()
		pp = -1
		for j in range(l(z)):
			if z[j] == '(':
				a += 1
			else:
				b += 1
			if pp == -1:
				s.append(z[j])
				pp = z[j]
				continue
			if pp == '(' and z[j] == ')':
				s.pop()
				b -= 1
				a -= 1
				if not s:
					pp = -1
				else:
					pp = s[-1]
			else:
				s.append(z[j])
				pp = z[j]
		if a == 0 or b == 0:
			if (a, b) not in p:
				p[a, b] = 1
			else:
				p[a, b] += 1
	pairs = 0
	f = 1
	while True:
		f = 1
		for (key, value) in p.items():
			if key == (0, 0):
				pairs += value // 2
				del p[0, 0]
				f = 0
				break
			temp = (key[-1], key[0])
			if temp in p:
				pairs += min(p[temp], value)
				del p[key]
				del p[temp]
				f = 0
				break
		if f:
			break
	print(pairs)


cor = 0
(x, y) = (dict(), dict())
for _ in range(int(input())):
	s = input()
	stack = 0
	(a, b) = (0, 0)
	for c in s:
		if c == '(':
			stack += 1
		elif c == ')':
			if stack == 0:
				a += 1
			else:
				stack -= 1
	b = stack
	if a == 0 and b == 0:
		cor += 1
	elif a == 0:
		if b in y:
			y[b] += 1
		else:
			y[b] = 1
	elif b == 0:
		if a in x:
			x[a] += 1
		else:
			x[a] = 1
cor = cor // 2
for k in x:
	if k in y:
		cor += min(x[k], y[k])
print(cor)


n = int(input())
DPos = {}
DNeg = {}
z = 0
for _ in range(n):
	s = input()
	w = 0
	t = 0
	for i in s:
		if i == '(':
			t += 1
		else:
			t -= 1
			w = min(w, t)
	if t > 0:
		if w >= 0:
			if t in DPos:
				DPos[t].append((w, t))
			else:
				DPos[t] = [(w, t)]
	elif t < 0:
		if w == t:
			if t in DNeg:
				DNeg[t].append((w, t))
			else:
				DNeg[t] = [(w, t)]
	elif w == 0:
		z += 1
ans = z // 2
for k in DPos:
	if -k in DNeg:
		ans += min(len(DPos[k]), len(DNeg[-k]))
print(ans)


from collections import deque

def get_required(expr):
	open_required = 0
	stack = deque([])
	for s in expr:
		if s == ')':
			if len(stack):
				stack.pop()
			else:
				open_required += 1
		elif s == '(':
			stack.append('(')
	if open_required and len(stack):
		return None
	if open_required:
		return open_required
	return -len(stack)

def pairs_count(n, arr):
	requires = []
	for i in range(n):
		req = get_required(arr[i])
		if req is not None:
			requires.append(req)
	requires.sort()
	start = 0
	end = len(requires) - 1
	matches = 0
	while end > start:
		s = requires[start] + requires[end]
		if s == 0:
			matches += 1
			start += 1
			end -= 1
		elif s < 0:
			start += 1
		else:
			end -= 1
	return matches
n = int(input())
arr = [None] * n
for i in range(n):
	arr[i] = input()
print(pairs_count(n, arr))


n = int(input())
a = []
for i in range(n):
	s = input()
	stack = []
	for j in range(len(s)):
		if len(stack) == 0:
			stack.append(s[j])
		elif stack[-1] == '(' and s[j] == ')':
			stack.pop()
		else:
			stack.append(s[j])
	if '(' in stack and ')' in stack:
		continue
	sums = 0
	if '(' in stack:
		sums = len(stack)
	else:
		sums = -len(stack)
	a.append(sums)
dp = {}
dn = {}
for i in a:
	if i < 0:
		if i not in dn:
			dn[i] = 0
		dn[i] += 1
	else:
		if i not in dp:
			dp[i] = 0
		dp[i] += 1
ans = 0
for i in dp:
	if i == 0:
		ans = ans + dp[i] // 2
	elif -i in dn:
		ans = ans + min(dp[i], dn[-i])
print(ans)


def balance(a):
	ct = 0
	if a[-1] == '(':
		for i in range(len(a)):
			if a[i] == '(':
				ct += 1
			else:
				ct -= 1
				if ct < 0:
					return None
	elif a[0] == ')':
		for i in range(len(a) - 1, -1, -1):
			if a[i] == ')':
				ct += 1
			else:
				ct -= 1
				if ct < 0:
					return None
		ct = -ct
	else:
		for i in range(len(a)):
			if a[i] == '(':
				ct += 1
			else:
				ct -= 1
		if ct >= 0:
			ct2 = 0
			for i in range(len(a)):
				if a[i] == '(':
					ct2 += 1
				else:
					ct2 -= 1
					if ct2 < 0:
						return None
		else:
			ct2 = 0
			for i in range(len(a) - 1, -1, -1):
				if a[i] == ')':
					ct2 += 1
				else:
					ct2 -= 1
					if ct2 < 0:
						return None
	return ct
n = int(input())
B = {}
C = []
z = 0
for _ in range(n):
	x = input()
	q = balance(x)
	if q != None:
		if q > 0:
			if q in B:
				B[q] += 1
			else:
				B[q] = 1
		elif q < 0:
			C.append(q)
		else:
			z += 1
ct = 0
for e in C:
	if -e in B:
		ct += 1
		if B[-e] == 1:
			B.pop(-e)
		else:
			B[-e] -= 1
print(ct + z // 2)


d = [0] * 1000001
for _ in [0] * int(input()):
	m = c = 0
	for x in input():
		c += 2 * (x < ')') - 1
		m = min(m, c)
	d[c] += m in (0, c)
print((sum(map(min, zip(d[1:], d[::-1]))) + d[0]) // 2)


import sys
input = sys.stdin.readline
n = int(input())
ls = [input().replace('\n', '') for i in range(n)]
cnt = [0 for i in range(n)]
for i in range(n):
	(a, b) = (0, 0)
	st = []
	for c in ls[i]:
		if not st:
			st.append(c)
		elif c == '(':
			st.append(c)
		elif st[-1] == '(' and c == ')':
			st.pop()
		else:
			st.append(c)
	for c in st:
		if c == ')':
			a += 1
		else:
			b += 1
	cnt[i] = [a, b]
k = 0
from collections import defaultdict
(op, en) = (defaultdict(int), defaultdict(int))
for i in range(n):
	(x, y) = cnt[i]
	if not x and (not y):
		k += 1
	elif not x or not y:
		if not x:
			en[y] += 1
		else:
			op[x] += 1
ans = k // 2
for i in op:
	ans += min(op[i], en[i])
print(ans)


from collections import Counter
n = int(input())
arr = []

def getSeqValue(s):
	a = 0
	b = 0
	stack = []
	for x in s:
		if x == ')':
			if stack:
				stack.pop()
			else:
				a += 1
		else:
			stack.append('(')
	b = len(stack)
	return (a, b)
for i in range(n):
	inp = input()
	arr.append(getSeqValue(inp))
c = Counter(arr)
res = 0
res += c[0, 0] // 2
c[0, 0] = 0
for key in c:
	(a, b) = key
	if a != 0 and b != 0:
		continue
	res += min(c[a, b], c[b, a])
	c[a, b] = 0
	if (b, a) in c:
		c[b, a] = 0
print(res)


def get_num(val):
	stack = []
	for x in val:
		if x is '(':
			stack.append('(')
		elif len(stack):
			if stack[-1] == '(':
				stack.pop()
			else:
				stack.append(x)
		else:
			stack.append(x)
	return ''.join(stack)

def weight_count(x):
	if '(' in x:
		return len(x)
	else:
		return -len(x)
n = int(input())
l = []
for x in range(n):
	l.append(input())
par = [get_num(x) for x in l]
pre = [x for x in par if len(x) == 0]
prelen = len(pre) // 2
valid_par = [x for x in par if len(set(x)) == 1]
w = [weight_count(x) for x in valid_par]
d_p = {}
d_n = {}
for x in w:
	if x > 0:
		d_p[x] = d_p.get(x, 0) + 1
	else:
		d_n[x] = d_n.get(x, 0) + 1
s = 0
for (key, value) in d_n.items():
	val = d_p.get(-key, 0)
	s += min(val, value)
print(s + prelen)


t = int(input())
from collections import Counter
l = []
for i in range(t):
	s = input()
	left_angle = 0
	right_angle = 0
	for j in range(len(s)):
		current = s[j]
		if left_angle == 0 and current == ')':
			right_angle += 1
		elif left_angle != 0 and current == ')':
			left_angle -= 1
		else:
			left_angle += 1
	if left_angle == 0 and right_angle != 0:
		l.append(-right_angle)
	elif left_angle != 0 and right_angle == 0:
		l.append(left_angle)
	elif left_angle == 0 and right_angle == 0:
		l.append(0)
l.sort()
val = Counter(l)
total = 0
for j in val:
	if j == 0:
		total += val[j] // 2
	elif val[j] != 0 and val[-j] != 0:
		count = min(val[j], val[-j])
		val[j] -= count
		val[-j] -= count
		total += count
print(total)


n = int(input())
openleft = {}
openright = {}
correctbracketseq = 0
pairs = 0
for i in range(n):
	seq = input()
	sum = 0
	left = 0
	right = 0
	for b in seq:
		if b == ')' and right == 0:
			left += 1
		elif b == ')' and right > 0:
			right -= 1
		elif b == '(':
			right += 1
	if right > 0 and left > 0:
		continue
	elif right == 0 and left == 0:
		correctbracketseq += 1
	elif left > 0:
		if left in openright.keys():
			if openright[left] > 0:
				openright[left] = openright[left] - 1
				pairs += 1
				if openright[left] == 0:
					openright.pop(left, None)
			elif left in openleft.keys():
				openleft[left] = openleft[left] + 1
			else:
				openleft[left] = 1
		elif left in openleft.keys():
			openleft[left] = openleft[left] + 1
		else:
			openleft[left] = 1
	elif right > 0:
		if right in openleft.keys():
			if openleft[right] > 0:
				openleft[right] = openleft[right] - 1
				pairs += 1
				if openleft[right] == 0:
					openleft.pop(right, None)
			elif right in openright.keys():
				openright[right] = openright[right] + 1
			else:
				openright[right] = 1
		elif right in openright.keys():
			openright[right] = openright[right] + 1
		else:
			openright[right] = 1
pairs += correctbracketseq // 2
print(pairs)


from collections import defaultdict

def zeror():
	return 0

def clear(strr):
	stc = []
	for b in strr:
		if len(stc) == 0 or b == '(':
			stc.append(b)
		elif stc[-1] == '(':
			stc.pop()
		else:
			stc.append(')')
	return stc

def open_close(bracs):
	op = []
	cl = []
	for el in bracs:
		if len(el) != 0:
			if el[0] == '(' == el[-1]:
				op.append(len(el))
			elif el[0] == ')' == el[-1]:
				cl.append(len(el))
	return (op, cl)

def solve(op, cl):
	ans = 0
	closed = defaultdict(zeror)
	for c in cl:
		closed[c] += 1
	for o in op:
		if o in closed.keys():
			ans += 1
			closed[o] -= 1
			if closed[o] == 0:
				del closed[o]
	return ans

def main():
	ful = 0
	arr = []
	n = int(input())
	for _ in range(n):
		tem = clear(input())
		if len(tem) != 0:
			arr.append(tem)
		else:
			ful += 1
	(openB, closeB) = open_close(arr)
	print(solve(openB, closeB) + ful // 2)
main()


n = int(input())
a = []
for i in range(n):
	s = input()
	k = 0
	k_min = 0
	for c in s:
		if c == '(':
			k += 1
		else:
			k -= 1
			if k < k_min:
				k_min = k
	if k >= 0:
		if k_min >= 0:
			a.append(k)
	elif k_min >= k:
		a.append(k)
a.sort(reverse=True)
count = 0
left = 0
rigth = len(a) - 1
while left < rigth:
	if a[left] > -a[rigth]:
		left += 1
	elif a[left] < -a[rigth]:
		rigth -= 1
	else:
		count += 1
		left += 1
		rigth -= 1
print(count)


import collections
n = int(input())
left = collections.defaultdict(int)
right = collections.defaultdict(int)
correct = 0
for _ in range(n):
	l = 0
	r = 0
	s = input()
	for x in s:
		if x == '(':
			l += 1
		elif l > 0:
			l -= 1
		else:
			r += 1
	if l == 0 and r != 0:
		right[r] += 1
	elif l != 0 and r == 0:
		left[l] += 1
	elif l == 0 and r == 0:
		correct += 1
ans = correct // 2
for k in left.keys():
	mini = min(left[k], right[k])
	left[k] -= mini
	right[k] -= mini
	ans += mini
print(ans)


n = int(input())
arr = []
for i in range(n):
	s = input()
	l = r = 0
	for x in s:
		if x == ')' and r == 0:
			l += 1
		elif x == ')':
			r -= 1
		else:
			r += 1
	if l > 0 and r > 0:
		continue
	else:
		arr.append(-l + r)
arr.sort()
l = cnt = 0
r = len(arr) - 1
while r > l:
	if -arr[l] < arr[r]:
		r -= 1
		continue
	if -arr[l] > arr[r]:
		l += 1
		continue
	if arr[l] + arr[r] == 0:
		cnt += 1
		r -= 1
		l += 1
print(cnt)


from collections import defaultdict
n = int(input())
S = [input() for i in range(n)]
C = defaultdict(int)
for ss in S:
	t = ''
	left = 0
	right = 0
	for s in ss:
		if s == '(':
			left += 1
		elif left > 0:
			left -= 1
		else:
			right += 1
	if left > 0 and right > 0:
		continue
	if left == 0 and right == 0:
		C[0] += 1
		continue
	if left > 0:
		C[left] += 1
	else:
		C[-right] += 1
ans = 0
C[0] //= 2
for k in filter(lambda k: k >= 0, C.keys()):
	ans += min(C[k], C.get(k * -1, 0))
print(ans)


import sys, os
from math import sqrt, gcd, ceil, log, floor
from math import factorial as fact
from bisect import bisect, bisect_left
from collections import defaultdict, Counter, deque
from heapq import heapify, heappush, heappop
from itertools import permutations
input = sys.stdin.readline
read = lambda : list(map(int, input().strip().split()))
MOD = 10 ** 9 + 7

def l(s):
	c = 0
	for i in s:
		if i == '(':
			c += 1
		else:
			c -= 1
		if c < 0:
			return -1
	return c

def r(s):
	c = 0
	for i in s[::-1]:
		if i == ')':
			c += 1
		else:
			c -= 1
		if c < 0:
			return -1
	return c

def main():
	ans_ = []
	ans = 0
	left = defaultdict(int)
	right = defaultdict(int)
	for i in range(int(input())):
		s = input().strip()
		(n, m) = (l(s), r(s))
		if n != -1:
			left[n] += 1
		else:
			right[m] += 1
	for i in left:
		ans += min(left[i], right[i])
	ans += left[0] // 2
	print(ans)
main()


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()


from collections import Counter
n = int(input())
l = []
for i in range(n):
	s = input()
	(count, temp) = (0, 0)
	for j in s:
		if j == '(':
			count += 1
		else:
			count -= 1
		temp = min(temp, count)
	if temp >= min(0, count):
		l.append(count)
c = Counter(l)
ans = 0
for i in range(1, 300000):
	if i in c:
		if -1 * i in c:
			ans += min(c[i], c[-1 * i])
if 0 in c:
	ans += c[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)]
v = [cnt(x) for x in s]
v = [x for x in v if x is not None]
v.sort()
v = collections.deque(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)


n = int(input())
left = [0 for i in range(500010)]
right = [0 for i in range(500010)]
none = 0
ans = 0
for i in range(n):
	str = input()
	b = 0
	h = 0
	for i in str:
		if b == 0 and i == '(':
			b += 1
		elif b == 0 and i == ')':
			h += 1
		elif i == ')':
			b -= 1
		else:
			b += 1
	if h > 0:
		if b == 0:
			if left[h] > 0:
				left[h] -= 1
				ans += 1
			else:
				right[h] += 1
	elif b == 0:
		if none > 0:
			none = 0
			ans += 1
		else:
			none = 1
	elif right[b] > 0:
		right[b] -= 1
		ans += 1
	else:
		left[b] += 1
print(ans)


def count_seq(line):
	(o, c) = (0, 0)
	for (i, e) in enumerate(line):
		if e == ')':
			if o > 0:
				o -= 1
			else:
				c += 1
		else:
			o += 1
	return (c, o)
n = int(input().strip())
pairs = {}
for seqence_num in range(1, n + 1):
	line = input().strip()
	(l, r) = count_seq(line)
	can_make_pair = l == 0 or r == 0
	if not can_make_pair:
		continue
	if l > 0:
		pairs[-l] = pairs[-l] + 1 if -l in pairs else 1
	elif r > 0:
		pairs[r] = pairs[r] + 1 if r in pairs else 1
	else:
		pairs[0] = pairs[0] + 1 if 0 in pairs else 1
count = 0
for k in pairs:
	if k > 0:
		if -k in pairs:
			count += min(pairs[-k], pairs[k])
count += pairs[0] // 2 if 0 in pairs else 0
print(count)


n = int(input())
left = dict()
right = dict()
for _ in range(n):
	s = input()
	p = 0
	mi = 0
	for c in s:
		if c == '(':
			p += 1
		else:
			p -= 1
		if p <= mi:
			mi = p
	if mi >= 0:
		if p not in left:
			left[p] = 0
		left[p] += 1
	if p <= 0 and mi >= p:
		if p not in right:
			right[p] = 0
		right[p] += 1
r = 0
for (k, _) in left.items():
	if k == 0:
		r += left[k] // 2
	elif -k in right:
		r += min(left[k], right[-k])
print(r)


MOD = 1000000007
ii = lambda : int(input())
si = lambda : input()
dgl = lambda : list(map(int, input()))
f = lambda : map(int, input().split())
il = lambda : list(map(int, input().split()))
ls = lambda : list(input())
ln = [0] * (5 * 10 ** 5 + 10)
lp = [0] * (5 * 10 ** 5 + 10)
z = 0
for _ in range(ii()):
	s = si()
	l = []
	for i in s:
		if l == []:
			l.append(i)
		elif i == ')':
			if l[-1] == '(':
				l.pop()
			else:
				l.append(i)
		else:
			l.append(i)
	p = sum((i == '(' for i in l))
	n = sum((i == ')' for i in l))
	if p > 0 and n > 0:
		continue
	elif p > 0:
		lp[p] += 1
	elif n > 0:
		ln[n] += 1
	else:
		z += 1
ans = 0
for (i, j) in zip(ln, lp):
	ans += min(i, j)
print(ans + z // 2)


def cleaning(string):
	aux = []
	for i in string:
		if not len(aux):
			aux.append(i)
			continue
		if aux[-1] == '(' and i == ')':
			aux.pop()
			continue
		aux.append(i)
	return ''.join(aux)

def C():
	n = int(input())
	pairs = 0
	counterLeft = {}
	counterRight = {}
	emptys = 0
	for i in range(n):
		s = cleaning(input())
		if not s:
			emptys += 1
			continue
		if '(' in s and ')' in s:
			continue
		if '(' in s:
			if len(s) in counterLeft:
				counterLeft[len(s)] += 1
			else:
				counterLeft[len(s)] = 1
		if ')' in s:
			if len(s) in counterRight:
				counterRight[len(s)] += 1
			else:
				counterRight[len(s)] = 1
	pairs += emptys // 2
	for i in counterLeft:
		if i not in counterRight:
			continue
		pairs += min(counterLeft[i], counterRight[i])
	print(pairs)
C()


n = int(input())
m1 = [0] * (10 ** 6 + 10)
ze = 0
m2 = [0] * (10 ** 6 + 10)
for i in range(n):
	s = input()
	(temp1, temp2) = (0, 0)
	for j in s:
		if j == '(':
			temp1 += 1
		elif temp1 == 0:
			temp2 += 1
		else:
			temp1 -= 1
	if temp1 != 0 and temp2 != 0:
		continue
	if temp1 == 0 and temp2 == 0:
		ze += 1
	else:
		m1[temp1] += 1
		m2[temp2] += 1
ans = 0
for i in range(1, 10 ** 6 + 10):
	ans += min(m1[i], m2[i])
print(ans + ze // 2)


def residue(sequence):
	size = len(sequence)
	a = []
	for i in range(0, size):
		char = sequence[i]
		if char == '(':
			a.append(char)
		elif len(a) and a[-1] == '(':
			a.pop()
		else:
			a.append(char)
	return (a.count(')'), a.count('('))
n = int(input(''))
s = [''] * 100001
cor = 0
incor = []
pairs = 0
left = {}
right = {}
for i in range(0, n):
	seq = str(input(''))
	(a, b) = residue(seq)
	if a + b:
		if not a * b:
			if a:
				try:
					left[a] += 1
				except:
					left[a] = 1
			else:
				try:
					right[b] += 1
				except:
					right[b] = 1
	else:
		cor += 1
pairs += int(cor / 2)
for key in left:
	on_left = left[key]
	try:
		on_right = right[key]
		cur_pairs = min(on_left, on_right)
		pairs += cur_pairs
	except:
		{}
print(pairs)


from sys import stdin
input = lambda : stdin.readline().rstrip()
n = int(input())
big = {}
smol = {}
ans = 0
goods = 0
for _ in range(n):
	cs = 0
	good = 1
	mn = 0
	mx = 0
	for i in input():
		if i == ')':
			cs -= 1
			mx -= 1
		else:
			cs += 1
			mx += 1
		mn = min(mn, cs)
		mx = max(0, mx)
	if cs or mn:
		good = 0
	if mx and mn:
		continue
	if good:
		goods += 1
	elif mn:
		if big.get(-mn):
			ans += 1
			big[-mn] -= 1
		else:
			smol[mn] = smol.get(mn, 0) + 1
	elif smol.get(-cs):
		ans += 1
		smol[-cs] -= 1
	else:
		big[cs] = big.get(cs, 0) + 1
ans += goods // 2
print(ans)


import sys
from collections import defaultdict
H = defaultdict(lambda : 0)
for _ in range(int(input())):
	s = input()
	stack = []
	for i in s:
		if not stack:
			stack.append(i)
			continue
		if stack[-1] == '(' and i == ')':
			stack.pop()
			continue
		stack.append(i)
	l = stack.count('(')
	r = len(stack) - l
	if l * r:
		continue
	H[(1 - 2 * (l == 0)) * (l + r)] += 1
dans = H[0] // 2 * 2
H[0] = 0
for j in H.copy().keys():
	dans += min(H[j], H[-j])
print(dans // 2)


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
	elif -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)


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)
main()


def tallies(s):
	right = 0
	needleft = 0
	for char in s:
		if char == '(':
			right += 1
		elif right > 0:
			right -= 1
		else:
			needleft += 1
	return [needleft, right]

def better(strings):
	outputleft = []
	outputright = []
	finished = 0
	for s in strings:
		new = tallies(s)
		if new == [0, 0]:
			finished += 1
		elif new[1] == 0:
			outputleft.append(new[0])
		elif new[0] == 0:
			outputright.append(new[1])
	return (outputleft, outputright, int(finished / 2))

def final(strings):
	(nextleft, nextright, good) = better(strings)
	if len(nextleft) == 0 or len(nextright) == 0:
		return good
	nextleft.sort()
	nextright.sort()
	biggest = min(nextleft[-1], nextright[-1])
	output = good
	for need in range(biggest + 1):
		left = 0
		right = 0
		for (i, el) in enumerate(nextleft):
			if el == need:
				left += 1
			elif el != need:
				nextleft = nextleft[i:]
				break
		for (i, el) in enumerate(nextright):
			if el == need:
				right += 1
			elif el != need:
				nextright = nextright[i:]
				break
		output += min(left, right)
	return output
n = int(input())
strings = []
for i in range(n):
	strings.append(input())
output = final(strings)
print(output)


def check_para(v):
	d = {'(': 1, ')': -1}
	s = [v[0]]
	for i in v[1:]:
		if s and s[-1] == '(' and (i == ')'):
			_ = s.pop()
		else:
			s.append(i)
	s = ''.join(s)
	if ')(' in s:
		return None
	s = [d[i] for i in s]
	return sum(s)
n = int(input())
s = []
for i in range(n):
	v = input()
	v = check_para(v)
	if v is not None:
		s.append(v)
d = {}
out = 0
for i in s:
	if d.get(-i, 0):
		d[-i] -= 1
		out += 1
	else:
		d[i] = d.get(i, 0) + 1
print(out)


import sys
from itertools import *

def ev(S):
	stack = []
	for s in S:
		if s == '(':
			stack.append('(')
		elif len(stack) and stack[-1] == '(':
			stack.pop()
		else:
			stack.append(')')
	return stack
AA = [s.strip() for s in sys.stdin.readlines()[1:]]
Z = []
W = []
balanced = 0
for aa in AA:
	x = ev(aa)
	if not len(x):
		balanced += 1
		continue
	if ')' in x and '(' in x:
		continue
	if ')' in x:
		Z.append(len(x))
	if '(' in x:
		W.append(len(x))
q = balanced // 2
for a in set(Z).intersection(set(W)):
	q += min(Z.count(a), W.count(a))
print(q)


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
for i in list(left.keys()):
	ans += min(left[i], right[i]) if i != 0 else left[i] // 2
print(ans)


def count(s):
	m = 0
	c = 0
	for i in s:
		if i == '(':
			c += 1
		if i == ')':
			c -= 1
		m = min(m, c)
	return (c, m)
n = int(input())
d = {}
for _ in range(n):
	(c, m) = count(input())
	if not (m < 0 and m < c):
		d[c] = d.get(c, 0) + 1
ans = 0
for i in d.keys():
	if -i in d:
		if i == 0:
			ans += d[i] // 2
		else:
			ans += min(d[i], d[-i])
			d[i] = d[-i] = 0
print(ans)


from collections import defaultdict

def ok(ls):
	opens = 0
	unopened = 0
	for x in ls:
		if x:
			opens += 1
		elif opens > 0:
			opens -= 1
		else:
			unopened += 1
	return (opens > 0, unopened > 0, opens, unopened)
ls = []
for _ in range(int(input())):
	ls.append(ok([i == '(' for i in input()]))
total = 0
ends = defaultdict(int)
starts = defaultdict(int)
for ans in ls:
	if ans[0]:
		if ans[1]:
			continue
		starts[ans[2]] += 1
	elif ans[1]:
		ends[ans[3]] += 1
	else:
		total += 1
total = total // 2
used = [False for _ in starts]
for i in ends:
	total += min(ends[i], starts[i])
print(total)


def bracket(s):
	leftBQ = 0
	openRightB = 0
	for i in s:
		if i == '(':
			leftBQ += 1
		elif leftBQ > 0:
			leftBQ -= 1
		else:
			openRightB += 1
	if leftBQ > 0 and openRightB > 0:
		return (-1, -1)
	if leftBQ > 0:
		return (1, leftBQ)
	if openRightB > 0:
		return (0, openRightB)
	return (1, 0)
n = int(input())
d = [[0 for j in range(500006)] for i in range(2)]
res = 0
for i in range(n):
	s = input()
	(r, b) = bracket(s)
	if r == -1 and b == -1:
		continue
	if d[r][b] > 0:
		d[r][b] -= 1
		res += 1
	elif b != 0:
		d[abs(r - 1)][b] += 1
	else:
		d[r][b] += 1
print(res)


n = int(input())
a = []
set = set()
pairs = 0
dict = {}
for s in range(n):
	skobki = 0
	c = input()
	open = False
	open_reverse = False
	tmp = 0
	for i in range(len(c)):
		if c[i] == ')':
			skobki -= 1
			if open and tmp > 0:
				tmp -= 1
			elif open and tmp == 0:
				open = False
			else:
				open_reverse = True
		else:
			if open == True:
				tmp += 1
			else:
				open = True
			skobki += 1
	if open_reverse and open:
		pass
	else:
		a.append(skobki)
for elem in a:
	if -elem in set:
		pairs += 1
		if dict.get(-elem, 1) > 1:
			dict[-elem] = dict.get(-elem, 1) - 1
		else:
			set.discard(-elem)
	elif elem in set:
		dict[elem] = dict.get(elem, 1) + 1
	else:
		set.add(elem)
print(pairs)


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
from collections import *
input = sys.stdin.readline
sys.setrecursionlimit(100000)

def li():
	return [int(i) for i in input().rstrip('\n').split(' ')]

def val():
	return int(input().rstrip('\n'))

def st():
	return input().rstrip('\n')

def sttoli():
	return [int(i) for i in input().rstrip('\n')]

def givevalues(s):
	t1 = t2 = 0
	for i in range(len(s)):
		if s[i] == '(':
			t1 += 1
		elif t1:
			t1 -= 1
		else:
			t2 += 1
	return [t1, t2]
n = val()
l = []
for i in range(n):
	l.append(st())
pval = [[0, 0] for i in range(n)]
d = defaultdict(int)
zeros = 0
for i in range(n):
	pval[i] = givevalues(l[i])
	if pval[i][0] and pval[i][1]:
		continue
	elif pval[i][0]:
		d[pval[i][0], 0] += 1
	elif pval[i][1]:
		d[pval[i][1], 1] += 1
	else:
		zeros += 1
tot = 0
for i in list(d):
	temp = min(d[i[0], not i[1]], d[i])
	d[i[0], not i[1]] -= temp
	d[i] -= temp
	tot += temp
print(tot + zeros // 2)


n = int(input())
d = {}
result = 0
for i in range(n):
	s = input()
	r = 0
	o = 0
	legit = True
	sub_z = False
	for c in s:
		if c == '(':
			r += 1
			if sub_z:
				o += 1
		else:
			r -= 1
			if sub_z and o > 0:
				o -= 1
		if r < 0:
			sub_z = True
	if sub_z and o > 0:
		legit = False
	if legit:
		ir = r * -1
		if ir in d and d[ir] > 0:
			d[ir] -= 1
			result += 1
		elif r not in d:
			d[r] = 1
		elif r in d:
			d[r] += 1
print(result)


from collections import *
d = (Counter(), Counter())
r = 0
for _ in [0] * int(input()):
	m = c = 0
	for x in input():
		c += 2 * (x < ')') - 1
		m = max(m, -c)
	if c == m == 0:
		r += 1
	elif m == 0 or c == -m:
		i = m > 0
		d[i][(c, m)[i]] += 1
print(sum((min(d[0][k], d[1][k]) for k in d[0])) + r // 2)


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)


import sys

def input():
	return sys.stdin.readline().strip()
from collections import deque, Counter
N = int(input())
aN = [input() for i in range(N)]
for i in range(N):
	stack = deque()
	for j in range(len(aN[i])):
		if aN[i][j] == '(':
			stack.append('(')
		elif len(stack) != 0:
			if stack[-1] == ')':
				stack.append(')')
			else:
				stack.pop()
		else:
			stack.append(')')
	aN[i] = {'l': stack.count('('), 'r': stack.count(')')}
cnt = {'l': Counter(), 'r': Counter(), 'lr': 0}
for i in range(N):
	if aN[i]['l'] == 0 and aN[i]['r'] == 0:
		cnt['lr'] += 1
	elif aN[i]['l'] == 0:
		cnt['r'][aN[i]['r']] += 1
	elif aN[i]['r'] == 0:
		cnt['l'][aN[i]['l']] += 1
ans = 0
for (k, v) in cnt['l'].items():
	ans += min(v, cnt['r'][k])
ans += cnt['lr'] // 2
print(ans)


n = int(input())
a = []
for i in range(n):
	s = input()
	a.append(s)
pust = 0
left_skobki = []
right_skobki = []

def p(m):
	global pust
	global left_skobki
	global right_skobki
	stack = []
	stack.append(m[0])
	for i in range(1, len(m)):
		if len(stack) == 0:
			stack.append(m[i])
		elif stack[len(stack) - 1] == '(' and m[i] == ')':
			stack.pop()
		else:
			stack.append(m[i])
	if stack.count('(') != 0 and stack.count(')') != 0:
		return 0
	elif stack.count('(') == 0 and stack.count(')') == 0:
		pust += 1
		return 0
	elif stack.count('(') == 0:
		right_skobki.append(stack.count(')'))
	else:
		left_skobki.append(stack.count('('))
for i in range(len(a)):
	p(a[i])
kol = 0
if len(left_skobki) == 0 or len(right_skobki) == 0:
	print(0 + pust // 2)
	exit()
else:
	for i in range(1, max(max(left_skobki), max(right_skobki)) + 1):
		if i in left_skobki and i in right_skobki:
			kol += min(left_skobki.count(i), right_skobki.count(i))
print(kol + pust // 2)


from collections import defaultdict
n = int(input())
d = defaultdict(int)
for i in range(n):
	a = input()
	st = []
	num = 0
	for j in a:
		if j == '(':
			st.append(j)
			num += 1
		else:
			num -= 1
			if len(st) and st[-1] == '(':
				st.pop(-1)
			else:
				st.append(j)
	if len(st) == 0:
		d[num] += 1
	elif st[0] == ')' and st[-1] == '(':
		pass
	else:
		d[num] += 1
ans = d[0] // 2
for k in d.keys():
	if k > 0 and -k in d:
		ans += min(d[k], d[-k])
print(ans)


n = int(input())
m1 = {}
m2 = {}
ans = 0
for i in range(n):
	count = 0
	mini = 0
	for j in input():
		if j == '(':
			count += 2
		count -= 1
		if mini > count:
			mini = count
	if count == 0 and mini == 0:
		ans += 1
	elif count > 0 and mini == 0:
		if count not in m1:
			m1[count] = 0
		m1[count] += 1
	elif mini == count:
		count *= -1
		if count not in m2:
			m2[count] = 0
		m2[count] += 1
ans = ans // 2
for x in m2:
	if x in m1:
		ans += min(m1[x], m2[x])
print(ans)


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)
		elif 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)


n = int(input())
l1 = []
l2 = []
z = 0
for i in range(0, n):
	s = input()
	x = 0
	y = 0
	flag = 0
	max = 0
	for c in s:
		if c == '(':
			x += 1
		else:
			y += 1
		if y > x:
			flag = 1
		if y - x > max:
			max = y - x
	if flag == 0:
		l1.append(x - y)
	elif x > y:
		continue
	elif max > y - x:
		continue
	else:
		l2.append(y - x)
l1.sort()
l2.sort()
a = 0
d = {}
for item in l1:
	if item not in d:
		d[item] = l1.count(item)
for key in d:
	z += min(d[key], l2.count(key))
f = l1.count(0)
z = z + f // 2
print(z)


n = int(input())
l = []
neg = []
pos = []
zero = []
for i in range(n):
	s = input()
	count = 0
	for x in s:
		if x == '(':
			count += 1
		else:
			count -= 1
	if count < 0:
		c = 0
		flag = True
		srev = s[::-1]
		for x in srev:
			if x == '(':
				c += 1
			else:
				c -= 1
			if c > 0:
				flag = False
				break
		if flag == True:
			neg.append(abs(count))
	elif count == 0:
		c = 0
		flag = True
		for x in s:
			if x == '(':
				c += 1
			else:
				c -= 1
			if c < 0:
				flag = False
				break
		if flag == True:
			zero.append(count)
	elif count > 0:
		c = 0
		flag = True
		for x in s:
			if x == '(':
				c += 1
			else:
				c -= 1
			if c < 0:
				flag = False
				break
		if flag == True:
			pos.append(count)
neg.sort()
pos.sort()
l1 = len(pos)
l2 = len(neg)
i = 0
j = 0
ans = 0
while i < l1 and j < l2:
	if pos[i] == neg[j]:
		ans += 1
		i += 1
		j += 1
	elif pos[i] < neg[j]:
		i += 1
	else:
		j += 1
ans += len(zero) // 2
print(ans)


n = int(input())
bracket = []
for _ in range(n):
	tmp = input()
	bracket.append(tmp)
cnt = [0 for i in range(n)]
min_cnt = [1000000000.0 for i in range(n)]
t = 500001
for i in range(len(bracket)):
	for j in range(len(bracket[i])):
		if bracket[i][j] == '(':
			cnt[i] += 1
		else:
			cnt[i] += -1
		min_cnt[i] = min(min_cnt[i], cnt[i])
number_z = [0 for i in range(t)]
number_f = [0 for i in range(t)]
cnt_zeros = 0
for i in range(len(cnt)):
	if cnt[i] > 0 and min_cnt[i] >= 0:
		number_z[int(cnt[i])] += 1
	elif cnt[i] < 0 and min_cnt[i] == cnt[i]:
		number_f[-int(cnt[i])] += 1
	elif cnt[i] == 0 and min_cnt[i] == 0:
		cnt_zeros += 1
tmp = 0
for i in range(len(number_z)):
	tmp += min(number_z[i], number_f[i])
pairs = tmp + int(cnt_zeros / 2)
print(int(pairs))


import sys
from itertools import accumulate
from collections import defaultdict
input()
(front, back) = [defaultdict(lambda : 0) for _ in range(2)]
for s in sys.stdin.read().split():
	s = [1 if _ == '(' else -1 for _ in s]
	if min(accumulate(s)) >= 0:
		front[sum(s)] += 1
	elif max(accumulate(reversed(s))) <= 0:
		back[-sum(s)] += 1
res = 0
for (x, cnt) in front.items():
	res += min(cnt, back[x])
res += -min(front[0], back[0]) + (front[0] + back[0]) // 2
print(res)


MAX_N = 5 * 10 ** 5 + 5

def main():
	n = int(input())
	ans = correct = 0
	(left, right) = ([0] * MAX_N, [0] * MAX_N)
	for i in range(n):
		s = input()
		ll = rr = 0
		for j in s:
			if j == '(':
				ll += 1
			elif not ll:
				rr += 1
			else:
				ll -= 1
		if ll and rr:
			continue
		elif ll:
			if right[ll]:
				ans += 1
				right[ll] -= 1
			else:
				left[ll] += 1
		elif rr:
			if left[rr]:
				ans += 1
				left[rr] -= 1
			else:
				right[rr] += 1
		elif correct:
			ans += 1
			correct -= 1
		else:
			correct += 1
	print(ans)
main()


n = int(input())
a = []
for i in range(0, n):
	s = input()
	s = s.rstrip()
	(op, cl, bal) = (0, 0, 0)
	for j in range(0, len(s)):
		if s[j] == '(':
			op += 1
		elif s[j] == ')':
			cl += 1
	for j in range(0, len(s)):
		if s[j] == '(':
			bal += 1
		elif s[j] == ')':
			if bal > 0:
				op -= 1
				cl -= 1
				bal -= 1
	if op > 0 and cl > 0:
		continue
	a.append(op - cl)
(ct, i, j) = (0, 0, len(a) - 1)
a.sort()
while i < j:
	if a[i] + a[j] == 0:
		i += 1
		ct += 1
		j -= 1
	elif a[i] + a[j] > 0:
		j -= 1
	else:
		i += 1
print(ct)


def check_seq(seq):
	openbrac = 0
	closebrac = 0
	for i in range(len(seq)):
		if seq[i] == '(':
			openbrac += 1
		elif seq[i] == ')':
			openbrac -= 1
		if openbrac < 0:
			closebrac += 1
			openbrac = 0
	return (openbrac, closebrac)
n = int(input())
correct = 0
incorrectopen = [0] * 500001
incorrectclose = [0] * 500001
comb = [0] * 500001
for case in range(n):
	bracs = input()
	[x, y] = check_seq(bracs)
	if [x, y] == [0, 0]:
		correct += 1
	elif x > 0 and y == 0:
		incorrectopen[x] += 1
		comb[x] = min(incorrectopen[x], incorrectclose[x])
	elif x == 0 and y > 0:
		incorrectclose[y] += 1
		comb[y] = min(incorrectopen[y], incorrectclose[y])
combos = correct // 2 + sum(comb)
print(combos)


n = int(input())
m = []
for j in range(n):
	s = input()
	stack = []
	countL = 0
	countR = 0
	for i in range(len(s)):
		if s[i] == '(':
			countR += 1
			stack.append('(')
		elif len(stack) > 0 and stack[-1] == '(':
			countR -= 1
			stack.pop(-1)
		else:
			stack.append(')')
			countL += 1
	if countL > 0 and countR > 0:
		pass
	elif countL > 0:
		m.append(0 - countL)
	else:
		m.append(countR)
m.sort()
r = 0
l = len(m) - 1
pare = 0
while r < l:
	if m[r] + m[l] == 0:
		r += 1
		l -= 1
		pare += 1
	elif m[r] + m[l] < 0:
		r += 1
	else:
		l -= 1
print(pare)


n = int(input())
good = set()
left = dict()
right = dict()
mid = 0
answer = 0
for i in range(n):
	inp = input()
	cou = 0
	inMinus = 0
	onPlus = 0
	for j in inp:
		if j == '(':
			cou += 1
			onPlus += 1
		else:
			cou -= 1
			if onPlus > 0:
				onPlus -= 1
		if cou < 0:
			inMinus = 1
	if cou < 0 and inMinus == 1 and (onPlus == 0):
		if abs(cou) in right:
			right[abs(cou)] += 1
		else:
			right[abs(cou)] = 1
	elif cou > 0 and inMinus == 0:
		if cou in left:
			left[cou] += 1
		else:
			left[cou] = 1
	elif cou == 0 and inMinus == 0:
		mid += 1
answer += mid // 2
for i in left.keys():
	if i in right:
		answer += min(left[i], right[i])
print(answer)


n = int(input())
ans = 0
s = []
for i in range(n):
	s += [input()]
d = {}
for i in s:
	p = [0, 0, 0]
	if i[0] == ')':
		p[0] = 1
	if i[-1] == '(':
		p[-1] = 1
	if p[0] == 1 and p[-1] == 1:
		continue
	k1 = 0
	ff1 = 0
	k = 0
	for j in i:
		if j == '(':
			k += 1
		else:
			k -= 1
	for j in i:
		if j == '(':
			k1 += 1
		else:
			k1 -= 1
		if k1 < 0:
			ff1 = 1
			break
	k2 = 0
	ff2 = 0
	for j in i[::-1]:
		if j == ')':
			k2 += 1
		else:
			k2 -= 1
		if k2 < 0:
			ff2 = 1
			break
	if ff1 == 1 and ff2 == 1:
		continue
	if ff1 == 1:
		p[0] = 1
	if ff2 == 1:
		p[2] = 1
	p[1] = k
	p = tuple(p)
	try:
		d[p] += 1
	except:
		d[p] = 1
c = 0
for i in d:
	p = i
	if p[0] == 0 and p[-1] == 0 and (p[1] == 0):
		c += d[i]
		continue
	elif p[0] == 0 and p[2] == 0:
		p1 = list(p)
		p1[1] = -p1[1]
		p1 = tuple(p1)
		try:
			k = min(d[p1], d[p])
			d[p1] -= k
			d[p] -= k
			ans += k
		except:
			continue
	else:
		p1 = list(p)
		p1[1] = -p1[1]
		p1[-1] = 1 - p1[-1]
		p1[0] = 1 - p1[0]
		p1 = tuple(p1)
		try:
			k = min(d[p1], d[p])
			d[p1] -= k
			d[p] -= k
			ans += k
		except:
			continue
ans += c // 2
print(ans)


n = int(input())
h = {}
p = 0
g = {}
for i in range(n):
	a = input()
	c = 0
	d = 0
	if a[0] == ')' and a[len(a) - 1] == '(':
		pass
	else:
		for i in range(len(a)):
			if a[i] == '(':
				c += 1
			else:
				c += -1
			if c < 0:
				d = 1
				c = 0
		if c == 0 and d == 1:
			if a.count(')') - a.count('(') in h.keys():
				h[a.count(')') - a.count('(')] += 1
			else:
				h[a.count(')') - a.count('(')] = 1
		elif c == 0 and d == 0:
			p += 1
		elif c > 0 and d == 1:
			pass
		elif c > 0 and d == 0:
			if a.count('(') - a.count(')') in g.keys():
				g[a.count('(') - a.count(')')] += 1
			else:
				g[a.count('(') - a.count(')')] = 1
count = 0
for i in h.keys():
	if i in g.keys():
		count += min(h[i], g[i])
print(count + p // 2)


import sys
import math

def read_int():
	return int(input().strip())

def read_int_list():
	return list(map(int, input().strip().split()))

def read_string():
	return input().strip()

def read_string_list(delim=' '):
	return input().strip().split(delim)
n = read_int()
scores = []

def score(seq):
	global scores
	uneven = ''
	stack = []
	for _s in seq:
		if _s == '(':
			stack.append('(')
		elif stack == []:
			uneven += ')'
		else:
			stack.pop()
	for e in stack:
		uneven += e
	if uneven.find('(') != -1 and uneven.find(')') != -1:
		return float('-inf')
	if uneven.find('(') != -1:
		return len(uneven)
	else:
		return -1 * len(uneven)
for i in range(n):
	seq = read_string()
	scores.append(score(seq))
scores.sort()
(forward, back) = (0, n - 1)
pairs = 0
while forward < back:
	temp = scores[forward] + scores[back]
	if temp == 0:
		forward += 1
		back -= 1
		pairs += 1
	elif temp < 0:
		forward += 1
	else:
		back -= 1
print(pairs)


n = int(input())
a = []
b = []
ok1 = []
ok2 = []
mp1 = [0 for i in range(0, 500005)]
mp2 = [0 for i in range(0, 500005)]
cnt = 0
for i in range(0, n):
	s = input()
	l = len(s)
	x = y = 0
	ok = 1
	for j in range(0, l):
		if s[j] == '(':
			x += 1
		else:
			y += 1
		if x < y:
			ok = 0
	ok1.append(ok)
	x = y = 0
	ok = 1
	for j in range(l - 1, -1, -1):
		if s[j] == '(':
			x += 1
		else:
			y += 1
		if x > y:
			ok = 0
	ok2.append(ok)
	a.append(x)
	b.append(y)
	if x == y and ok1[i] == 1 and (ok2[i] == 1):
		cnt += 1
	else:
		if ok1[i] == 1:
			mp1[x - y] += 1
		if ok2[i] == 1:
			mp2[y - x] += 1
ans = 0
for i in range(0, 500005):
	ans += min(mp1[i], mp2[i])
ans += cnt // 2
print(ans)


n = int(input())
data = {}
for _ in range(n):
	inp = input()
	s = []
	l_r = 0
	for x in inp:
		l_r += 1 if x == '(' else -1
		if len(s) == 0:
			s.append(x)
		elif x == '(':
			s.append(x)
		elif s[-1] == '(':
			s.pop()
		else:
			s.append(x)
	if '(' in s and ')' in s:
		continue
	if l_r in data:
		data[l_r] += 1
	else:
		data[l_r] = 1
ans = 0
for x in data:
	if x > 0 and -x in data:
		ans += min(data[x], data[-x])
if 0 in data:
	ans += data[0] // 2
print(ans)


n = int(input())
a = []
for i in range(n):
	a.append([1 if x == '(' else -1 for x in input().strip()])
lsms = []
for p in a:
	cs = 0
	ms = 0
	for e in p:
		cs += e
		ms = min(ms, cs)
	lsms.append([cs, ms])
lsms.sort(key=lambda sms: sms[1], reverse=True)
lsms.sort(key=lambda sms: sms[0], reverse=True)
l = 0
r = n - 1
ch = 0
while l < r:
	if lsms[l][0] + lsms[r][0] == 0:
		if lsms[l][1] < 0:
			l += 1
			continue
		if lsms[r][1] + lsms[l][0] < 0:
			r -= 1
			continue
		ch += 1
		l += 1
		r -= 1
	elif lsms[l][0] + lsms[r][0] < 0:
		r -= 1
		continue
	else:
		l += 1
		continue
print(ch)


n = int(input())
lefts = []
rights = []
either = 0
for i in range(n):
	s = input()
	partial = 0
	maxi = 0
	mini = 0
	(left, right) = (True, True)
	for char in s:
		if char == '(':
			partial += 1
		else:
			partial -= 1
			mini = min(partial, mini)
	if mini < 0:
		left = False
	if mini < partial:
		right = False
	if left:
		if right:
			either += 1
		else:
			lefts.append(partial)
	elif right:
		rights.append(-partial)
lefts.sort(reverse=True)
rights.sort(reverse=True)
if len(lefts) > 0 and len(rights) > 0:
	k = max(lefts[0], rights[0])
	lcounts = [0] * (k + 1)
	rcounts = [0] * (k + 1)
	for guy in lefts:
		lcounts[guy] += 1
	for guy in rights:
		rcounts[guy] += 1
	sumi = 0
	for i in range(k + 1):
		sumi += min(lcounts[i], rcounts[i])
	b = abs(lcounts[0] - rcounts[0])
	if b >= either:
		sumi += either
	else:
		sumi += b + (either - b) // 2
	print(sumi)
else:
	if len(lefts) > 0:
		a = lefts.count(0)
	else:
		a = rights.count(0)
	if a >= either:
		print(either)
	else:
		print(a + (either - a) // 2)


import sys
import collections
data = sys.stdin.read().splitlines()
n = int(data[0])
lines = data[1:]
m = collections.Counter()
ans = 0
for line in lines:
	total = 0
	for ch in line:
		total += 1 if ch == '(' else -1
	good = True
	cnt = 0
	for ch in line:
		cnt += 1 if ch == '(' else -1
		if cnt < min(total, 0):
			good = False
			break
	if not good:
		continue
	if m[-total] > 0:
		ans += 1
		m[-total] -= 1
	else:
		m[total] += 1
print(ans)


import sys
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)


def convert(string):
	cur = 0
	for i in string:
		if i == '(':
			cur += 1
		else:
			cur -= 1
		if cur < 0:
			break
	else:
		return cur
	cur = 0
	for i in string[::-1]:
		if i == '(':
			cur += 1
		else:
			cur -= 1
		if cur > 0:
			break
	else:
		return cur
	return None
num = int(input())
list_1 = []
for i in range(num):
	n = input()
	temp = convert(n)
	if temp != None:
		list_1.append(temp)
pos = []
neg = []
zeros = 0
num = 0
for i in list_1:
	if i == 0:
		zeros += 1
	if i < 0:
		neg.append(i)
	else:
		pos.append(i)
for i in set(pos):
	num += min(pos.count(i), neg.count(-i))
num += zeros // 2
print(num)


def check(s):
	f = c = inv = inva = 0
	for i in s:
		if i == '(':
			f += 1
		else:
			f -= 1
		if f < 0:
			inv = 1
	for i in range(len(s) - 1, -1, -1):
		if s[i] == ')':
			c += 1
		else:
			c -= 1
		if c < 0:
			inva = 1
	if inva + inv == 2:
		return [0, '~']
	elif c < f:
		return [c, 'c']
	elif c > f:
		return [f, 'f']
	else:
		return [0, 'o']
n = int(input())
ans1 = []
ans2 = []
ans = 0
for i in range(n):
	st = input()
	(a, b) = check(st)
	if b == 'c':
		ans1.append(a)
	elif b == 'f':
		ans2.append(a)
	elif b == 'o':
		ans += 1
ans = ans // 2
for i in range(len(ans1)):
	for j in range(len(ans2)):
		if ans1[i] == ans2[j]:
			ans2.pop(j)
			ans += 1
			break
print(ans)


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)


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)


def isCan(b, bal):
	st = []
	if bal < 0:
		st = [1] * -bal
	for i in range(len(b)):
		if b[i] == -1:
			if len(st) < 1 or st[-1] == -1:
				return False
			else:
				st.pop()
		else:
			st.append(1)
	if bal < 0 and len(st) == 0:
		return True
	elif bal > 0:
		if sum(st) == len(st) == bal:
			return True
	elif bal == 0 and len(st) == 0:
		return True
	return False
n = int(input())
summ = 0
rit = 0
p = {}
m = {}
for i in range(n):
	b = []
	bal = 0
	s = input()
	for c in s:
		if c == '(':
			bal += 1
			b.append(1)
		else:
			bal -= 1
			b.append(-1)
	if isCan(b, bal):
		if bal == 0:
			rit += 1
		elif bal > 0:
			p[bal] = p.get(bal, 0) + 1
		else:
			m[-bal] = m.get(-bal, 0) + 1
summ += rit // 2
for c in p.keys():
	summ += min(p.get(c, 0), m.get(c, 0))
print(summ)


n = int(input())
arr = []
limit = 10 ** 6 + 1
leftPart = [0 for x in range(limit)]
rightPart = [0 for x in range(limit)]
count = 0
for _ in range(n):
	next = input()
	if not (next[0] == ')' and next[-1] == '('):
		run = 0
		temp = 0
		stack = 0
		for c in next:
			if c == '(':
				stack += 1
			elif stack > 0:
				stack -= 1
			else:
				temp += 1
		if not (temp > 0 and stack > 0):
			if temp > 0:
				if rightPart[temp] > 0:
					rightPart[temp] -= 1
					count += 1
				else:
					leftPart[temp] += 1
			elif leftPart[stack] > 0:
				leftPart[stack] -= 1
				count += 1
			else:
				rightPart[stack] += 1
print(count + rightPart[0] // 2)


n = int(input())
a = []
ans = 0
for i in range(n):
	b = input()
	count = 0
	flag = 1
	for i in range(len(b)):
		if b[i] == '(':
			count += 1
		else:
			count -= 1
		if count < 0:
			flag = 0
			break
	if flag == 1:
		a.append(count)
	else:
		flag = 1
		count = 0
		for i in range(len(b) - 1, -1, -1):
			if b[i] == ')':
				count -= 1
			else:
				count += 1
			if count > 0:
				flag = 0
				break
		if flag == 1:
			a.append(count)
set_a = set(a)
for i in set_a:
	if i > 0:
		plus = a.count(i)
		minus = a.count(i * -1)
		ans += min(plus, minus)
ans += a.count(0) // 2
print(ans)


from functools import reduce
import math
from decimal import *

def factors(n):
	return set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0)))

def sol():
	am = int(input())
	n = []
	p = []
	po = []
	no = []
	nulls = []
	for i in range(am):
		data = list(input())
		pow = 0
		fl = False
		mi = 99999999
		for g in range(len(data)):
			if data[g] == '(':
				pow += 1
			else:
				pow -= 1
			mi = min(pow, mi)
			if pow < 0:
				fl = True
		if pow == 0 and (not fl):
			nulls.append(pow)
		elif pow > 0 and (not fl):
			p.append(pow)
			po.append(''.join(data))
		elif pow < 0 and pow == mi:
			no.append(''.join(data))
			n.append(-1 * pow)
	n.sort()
	p.sort()
	fInd = 0
	sInd = 0
	pair = len(nulls) // 2
	while fInd < len(n) and sInd < len(p):
		if n[fInd] != p[sInd]:
			if n[fInd] > p[sInd]:
				sInd += 1
			else:
				fInd += 1
		else:
			pair += 1
			fInd += 1
			sInd += 1
	print(pair)
sol()


n = int(input())
cl = {}
op = {}
sts = []
cp = 0
ans = 0
for i in range(n):
	s = input()
	st = []
	for j in s:
		if len(st) == 0:
			st.append(j)
		elif st[-1] == '(' and st[-1] != j:
			st.pop()
		else:
			st.append(j)
	a = st.count('(')
	b = st.count(')')
	if a == b == 0:
		cp += 1
	elif a == 0:
		r = op.get(b, 0)
		if r == 0:
			cl[b] = cl.get(b, 0) + 1
		else:
			ans += 1
			op[b] -= 1
	elif b == 0:
		r = cl.get(a, 0)
		if r == 0:
			op[a] = op.get(a, 0) + 1
		else:
			ans += 1
			cl[a] -= 1
print(ans + cp // 2)


n = int(input())
s = []
d = {}
for i in range(n):
	x = input()
	c = 0
	l = 0
	for j in x:
		if j == ')':
			c = c - 1
		else:
			c = c + 1
		if c < 0:
			l = l + 1
			c = 0
	if c > 0 and l == 0 or (l > 0 and c == 0) or (l == 0 and c == 0):
		c = c - l
		s.append(c)
		d[c] = d.get(c, 0) + 1
ans = 0
for i in range(len(s)):
	x = s[i]
	if d[x] > 0:
		if x == 0:
			if d[x] > 1:
				ans = ans + 1
				d[x] = d[x] - 2
		else:
			y = d.get(-x, 0)
			if y > 0:
				ans = ans + 1
				d[x] = d[x] - 1
				d[-x] = d[-x] - 1
print(ans)


left = [0 for i in range(1000000)]
right = [0 for i in range(1000000)]

def test(s):
	k = 0
	MIN = 0
	for i in range(len(s)):
		if s[i] == ')':
			k -= 1
			MIN = min(k, MIN)
		else:
			k += 1
	return MIN
n = int(input())
for i in range(n):
	l = 0
	s = input()
	for i in range(len(s)):
		if s[i] == '(':
			l += 1
		else:
			l -= 1
	judge = test(s)
	if l >= 0:
		if judge < 0:
			continue
		else:
			left[l] += 1
	elif judge < l:
		continue
	else:
		right[-l] += 1
ans = 0
for i in range(1, 500000):
	ans += min(right[i], left[i])
ans += left[0] >> 1
print(ans)


n = int(input())
l = [input() for i in range(n)]
(right, left, m) = ([], [], 0)
for s in l:
	(lb, rb, a, b) = (0, 0, 0, 0)
	for i in range(len(s)):
		if s[i] == '(':
			rb += 1
		else:
			rb -= 1
		if s[-1 - i] == ')':
			lb += 1
		else:
			lb -= 1
		if rb < 0:
			a = 1
		if lb < 0:
			b = 1
		if a and b:
			break
	else:
		if rb > 0:
			right.append(rb)
		elif rb < 0:
			left.append(lb)
		else:
			m += 1
m //= 2
for i in right:
	if i in left:
		m += 1
		left.remove(i)
print(m)


n = int(input())
arr = [0] * n
for i in range(0, n):
	str1 = input()
	s = 0
	for j in range(0, len(str1)):
		if str1[j] == ')':
			s -= 1
		else:
			s += 1
		if s < 0:
			s = 0
			arr[i] -= 1
	if s > 0 and arr[i] == 0:
		arr[i] += s
	elif s > 0 and arr[i] < 0:
		arr[i] = -1000000
arr.sort()
l = 0
r = n - 1
summ = 0
ss = set(arr)
for e in ss:
	if e > 0:
		summ += min(arr.count(e), arr.count(-1 * e))
summ += arr.count(0) // 2
print(summ)


from collections import Counter
n = int(input())
arr = [input() for _ in range(n)]
left = []
right = []
zero = []
for i in range(n):
	l = 0
	r = 0
	for x in arr[i]:
		if x == ')':
			if l > 0:
				l -= 1
			else:
				r += 1
		else:
			l += 1
	if l == 0 or r == 0:
		if l == 0 and r == 0:
			zero.append(0)
		if l == 0:
			right.append(r)
		elif r == 0:
			left.append(l)
left = Counter(left)
right = Counter(right)
c = 0
for x in left.keys():
	if x in right:
		c += min(left[x], right[x])
c += len(zero) // 2
print(c)


n = int(input())

def calc_num(bracket):
	out = 0
	left_count = 0
	right_count = 0
	first = True
	for (char_i, char) in enumerate(bracket):
		if char == '(':
			out += 1
			left_count += 1
		else:
			out += -1
			right_count += 1
		if left_count < right_count and first:
			left_count2 = 0
			right_count2 = 0
			first = False
			for char2 in bracket[::-1][:len(bracket) - char_i + 1]:
				if char2 == ')':
					left_count2 += 1
				else:
					right_count2 += 1
				if left_count2 < right_count2:
					return None
	if out > 0 and bracket[0] == ')' or (out < 0 and bracket[-1] == '('):
		out = None
	return out

def check_zero_status(bracket):
	if bracket[0] == ')':
		if bracket[-1] == '(':
			return None
		else:
			return -1
	elif bracket[-1] == '(':
		return 1
	else:
		return 0
plus_num_list = []
all_num_list = []
bracket_dict = {}
left_zero_num = 0
mid_zero_num = 0
right_zero_num = 0
for i in range(n):
	bracket = input()
	num = calc_num(bracket)
	if num == None:
		continue
	if num == 0:
		res = check_zero_status(bracket)
		if res is None:
			continue
		elif res == 1:
			left_zero_num += 1
		elif res == -1:
			right_zero_num += 1
		else:
			mid_zero_num += 1
	elif num in all_num_list:
		bracket_dict[num] += 1
	else:
		bracket_dict[num] = 1
		all_num_list.append(num)
		if num > 0:
			plus_num_list.append(num)
out = min(left_zero_num, right_zero_num) + mid_zero_num // 2
keyss = all_num_list
for num in plus_num_list:
	if -num in keyss:
		tmp = min(bracket_dict[num], bracket_dict[-num])
		out += tmp
print(out)


n = int(input())
arr = []
for i in range(n):
	s = str(input())
	arr.append(s)
dict1 = {}
dict2 = {}
for i in range(len(arr)):
	tempval = 0
	if arr[i][0] != ')' or arr[i][-1] != '(':
		if arr[i][0] == ')':
			tempval = 1
		else:
			tempval = 2
		if tempval == 1:
			count1 = 0
			count2 = 0
			val = 0
			flag = 0
			for j in range(len(arr[i]) - 1, -1, -1):
				if arr[i][j] == ')':
					count1 += 1
				else:
					count2 += 1
				if count2 > count1:
					flag = 1
			if count1 > count2 and flag == 0:
				try:
					dict1[count2 - count1] += 1
				except:
					KeyError
					dict1[count2 - count1] = 1
		else:
			count1 = 0
			count2 = 0
			val = 0
			flag = 0
			for j in arr[i]:
				if j == ')':
					count1 += 1
				else:
					count2 += 1
				if count1 > count2:
					flag = 1
			if flag == 1:
				count1 = 0
				count2 = 0
				val = 0
				flag = 0
				for j in range(len(arr[i]) - 1, -1, -1):
					if arr[i][j] == ')':
						count1 += 1
					else:
						count2 += 1
					if count2 > count1:
						flag = 1
				if count1 > count2 and flag == 0:
					try:
						dict1[count2 - count1] += 1
					except:
						KeyError
						dict1[count2 - count1] = 1
			elif count2 >= count1 and flag == 0:
				try:
					dict1[count2 - count1] += 1
				except:
					KeyError
					dict1[count2 - count1] = 1
ans = 0
for i in dict1.keys():
	if i == 0:
		dict1[i] = dict1[i] // 2
		ans += 2 * dict1[i]
	else:
		try:
			ans += min(dict1[i], dict1[-i])
		except:
			KeyError
print(ans // 2)


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
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)


n = int(input())
a = dict()
b = dict()
for i in range(n):
	s = input()
	k = 0
	max_k = 0
	op = True
	for j in s:
		if j == '(':
			k += 1
		else:
			k -= 1
			if k < max_k:
				max_k = k
		if k < 0:
			op = False
	if op == False and max_k < k:
		continue
	if op == True:
		if k in a.keys():
			a[k] += 1
		else:
			a[k] = 1
	elif k in b.keys():
		b[k] += 1
	else:
		b[k] = 1
ss = 0
for i in a.keys():
	if i == 0:
		ss += int(a[i] / 2)
	elif -i in b.keys():
		ss += min(a[i], b[-i])
print(ss)


c = {}
for _ in range(int(input())):
	a = input()
	(x, y) = (0, 0)
	for d in a:
		if '(' == d:
			x += 1
		else:
			x -= 1
		y = min(x, y)
	if y >= min(0, x):
		c[x] = c.get(x, 0) + 1
ans = 0
for x in c:
	if x < 0:
		ans += min(c[x], c.get(-x, 0))
ans += c.get(0, 0) // 2
print(ans)


def check(s):
	a = 0
	b = 0
	for c in s:
		if c == '(':
			a += 1
		else:
			a -= 1
		if a < 0:
			b += 1
			a = 0
	return (a, b)
n = int(input())
d = {}
for i in range(0, n):
	s = input()
	(a, b) = check(s)
	if a == 0 and b == 0:
		d[0] = d.get(0, 0) + 1
	elif a != 0 and b == 0:
		d[a] = d.get(a, 0) + 1
	elif b != 0 and a == 0:
		d[-b] = d.get(-b, 0) + 1
num = d.get(0, 0) // 2
for i in d:
	if i < 0 and d.get(i) and d.get(-i):
		num += min(d.get(i), d.get(-i))
print(num)


import sys
n = int(sys.stdin.readline().strip())
parsed = {}
for i in range(n):
	bracket = sys.stdin.readline().strip()
	(pre, post) = (0, 0)
	for char in bracket:
		if char == ')' and pre > 0:
			pre += -1
		elif char == ')':
			post += 1
		else:
			pre += 1
	if post == 0:
		parsed[pre] = parsed.get(pre, 0) + 1
	elif pre == 0:
		parsed[-1 * post] = parsed.get(-1 * post, 0) + 1
if 0 in parsed:
	pairs = parsed[0] // 2
else:
	pairs = 0
for (excess, count) in parsed.items():
	if excess > 0:
		pairs += min(count, parsed.get(-1 * excess, 0))
print(pairs)


import sys
import math
from collections import defaultdict

def getInputFromLine():
	return [int(x) for x in input().split()]
try:
	sys.stdin = open('input.txt', 'r')
	sys.stdout = open('output.txt', 'w')
except:
	pass

def mirror(s):
	s = s[::-1]
	m = ''
	for c in s:
		if c == ')':
			m += '('
		else:
			m += ')'
	return m

def getScore(s):
	score = 0
	for b in s:
		if b == '(':
			score += 1
		elif b == ')':
			score -= 1
		if score < 0:
			return -1
	return score
n = int(input())
brackets = []
for i in range(n):
	t = input()
	brackets.append(t)
scores = []
count = 0
bal = defaultdict(lambda : 0)
lead = 0
for b in brackets:
	balance = getScore(b)
	if balance != -1:
		bal[balance] += 1
	if balance == 0:
		lead += 1
for b in brackets:
	m = mirror(b)
	balance = getScore(m)
	if balance != -1:
		if bal[balance] > 0:
			bal[balance] -= 1
			count += 1
print(count - lead + lead // 2)


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

def check_par(s):
	stack = []
	op = 0
	cl = 0
	for i in range(len(s)):
		if s[i] == '(':
			stack.append(i)
		elif len(stack) == 0:
			op += 1
		else:
			stack.pop()
	stack.clear()
	for i in range(len(s) - 1, -1, -1):
		if s[i] == ')':
			stack.append(i)
		elif len(stack) == 0:
			cl += 1
		else:
			stack.pop()
	return (op, cl)

def getPairsCount(arr):
	from collections import Counter
	m = Counter(arr)
	count = 0
	for i in arr:
		if (i[1], i[0]) == i:
			count += m[i[1], i[0]] // 2
		else:
			count += min(m[i[1], i[0]], m[i[0], i[1]])
		m[i[1], i[0]] = 0
		m[i[0], i[1]] = 0
	return count
check = [tuple(check_par(par)) for par in pars]
check = list(filter(lambda x: x[0] == 0 or x[1] == 0, check))
print(getPairsCount(check))


srav = []

def push(x):
	srav.append(x)

def pop():
	return srav.pop()

def top():
	if size() == 0:
		return ''
	return srav[-1]

def size():
	return len(srav)

def clear():
	global srav
	srav = []
n = int(input())
a = []
b = dict()
ans = 0
for zx in range(n):
	s = input()
	x = s.count(')')
	x1 = s.count('(')
	clear()
	for i in range(len(s)):
		if s[i] == ')' and top() == '(':
			pop()
		else:
			push(s[i])
	if len(srav) != 0:
		if srav[0] == ')':
			if srav.count('(') != 0:
				continue
		elif srav[0] == '(':
			if srav.count(')') != 0:
				continue
	a.append(x1 - x)
for i in a:
	if -i in b and b[-i] != 0:
		b[-i] -= 1
		ans += 1
	else:
		try:
			b[i] += 1
		except:
			b[i] = 1
print(ans)


from collections import Counter
INFTY = -10 ** 6

def reduce(s):
	res = [')']
	cur_open = 0
	max_open = 0
	max_unopen_closed = 0
	for sk in s:
		if sk == '(':
			cur_open += 1
			if cur_open > 0:
				max_open = max(max_open, cur_open)
		else:
			cur_open -= 1
			if cur_open < 0:
				max_unopen_closed = max(max_unopen_closed, -cur_open)
	if max_unopen_closed > 0:
		if cur_open > -max_unopen_closed:
			return INFTY
	return cur_open
n = int(input().strip())
a = Counter()
for i in range(n):
	q = input().strip()
	a[reduce(q)] += 1
ps = a.keys()
res = 0
a[INFTY] = 0
for j in ps:
	if j != 0:
		cm = min(a[j], a[-j])
		if cm > 0:
			res += cm
			a[j] -= cm
			a[-j] -= cm
	else:
		res += a[0] // 2
print(res)


import os
import sys
from io import BytesIO, IOBase

def main():
	n = int(input())
	a = []
	for x in range(n):
		s = input()
		temp = []
		if len(s) == 1:
			if s == '(':
				a.append(1)
			else:
				a.append(-1)
			continue
		cnt = 0
		chk = 0
		tmp = 0
		for x in s:
			if x == '(':
				cnt += 1
				tmp += 1
			elif cnt == 0:
				chk = 1
				tmp -= 1
				cnt = 0
			else:
				cnt -= 1
				tmp -= 1
		if cnt > 0 and chk == 1:
			continue
		a.append(tmp)
	dic = {}
	n = len(a)
	ans = 0
	for x in range(n):
		if -a[x] in dic.keys():
			if dic[-a[x]] > 0:
				ans += 1
				dic[-a[x]] -= 1
			elif a[x] in dic.keys():
				dic[a[x]] += 1
			else:
				dic[a[x]] = 1
		elif a[x] in dic.keys():
			dic[a[x]] += 1
		else:
			dic[a[x]] = 1
	print(ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


def f(s):
	(s1, s2) = (0, 0)
	for i in s:
		if i == '(':
			s1 += 1
		elif s1 > 0:
			s1 -= 1
		else:
			s2 += 1
	return (s1, s2)
n = int(input())
A = []
B = []
(res, c) = (0, 0)
for i in range(n):
	(a, b) = f(input())
	if a == 0 and b == 0:
		c += 1
		if c == 2:
			res += 1
			c = 0
	elif a == 0:
		B.append(b)
	elif b == 0:
		A.append(a)
(d1, d2) = ({}, {})
for i in A:
	if i not in d1:
		d1[i] = 0
	d1[i] += 1
for i in B:
	if i not in d2:
		d2[i] = 0
	d2[i] += 1
for i in d1:
	if i in d2:
		res += min(d1[i], d2[i])
print(res)


import sys
from itertools import accumulate
from collections import Counter
input()
(front, back) = (Counter(), Counter())
for s in sys.stdin.read().split():
	s = [1 if _ == '(' else -1 for _ in s]
	if min(accumulate(s)) >= 0:
		front[sum(s)] += 1
	elif max(accumulate(reversed(s))) <= 0:
		back[-sum(s)] += 1
res = sum((front & back).values())
res += -min(front[0], back[0]) + (front[0] + back[0]) // 2
print(res)


import sys
input = sys.stdin.readline
n = int(input())
v = []
for _ in range(n):
	bkt = input()
	(l, r, mmin) = (0, 0, float('inf'))
	for item in bkt:
		if item == '(':
			l += 1
		elif item == ')':
			r += 1
		mmin = min(mmin, l - r)
	v.append([l - r, mmin])
v = sorted(v, key=lambda x: (x[0], x[1]))
ans = 0
(l, r) = (0, n - 1)
while l < r:
	(ll, llm) = v[l]
	(rr, rrm) = v[r]
	if rr < 0 or ll > 0:
		break
	if ll + rr > 0:
		r -= 1
	elif ll + rr < 0:
		l += 1
	elif rrm < 0:
		r -= 1
	elif rr + llm >= 0:
		ans += 1
		l += 1
		r -= 1
	else:
		l += 1
print(ans)


def mi():
	return map(int, input().split())
a = [0] * (5 * 10 ** 5 + 5)
b = [0] * (5 * 10 ** 5 + 5)
n = int(input())
corr = 0
for _ in range(n):
	s = list(input())
	t1 = t2 = 0
	l = len(s)
	for i in range(l):
		if s[i] == ')':
			if t1 == 0:
				t2 += 1
			else:
				t1 -= 1
		else:
			t1 += 1
	if t1 != 0 and t2 != 0:
		continue
	if t1 == 0 and t2 == 0:
		corr += 1
	else:
		a[t1] += 1
		b[t2] += 1
ans = corr // 2
for i in range(1, 500000 + 5):
	ans += min(a[i], b[i])
print(ans)


from collections import defaultdict as dd
n = int(input())
d = dd(int)
for i in range(n):
	s = list(input())
	(l, r, c) = (0, 0, 0)
	for x in s:
		if x == '(':
			c += 1
		else:
			c -= 1
			if c < 0:
				l += 1
				c = 0
	r = c
	d[l, r] += 1
x = list(d.keys()).copy()
ans = d[0, 0] // 2
for i in x:
	if i[0] != 0 or i[1] == 0:
		continue
	if d[i[1], 0] != 0:
		ans += min(d[i], d[i[1], 0])
print(ans)


import sys
aList = []
bList = []
correctSeq = 0
finalAns = 0

def giveValues(readInput):
	global aList
	global bList
	global correctSeq
	leftBraNeeded = 0
	rightBraNeeded = 0
	for x in readInput:
		if x == '(':
			rightBraNeeded += 1
		elif rightBraNeeded > 0:
			rightBraNeeded -= 1
		else:
			leftBraNeeded += 1
	if leftBraNeeded > 0 and rightBraNeeded > 0:
		return
	if leftBraNeeded == 0 and rightBraNeeded == 0:
		correctSeq += 1
		return
	if leftBraNeeded > 0:
		aList.append(leftBraNeeded)
		return
	else:
		bList.append(rightBraNeeded)
		return
numInput = int(sys.stdin.readline().strip())
for x in range(numInput):
	giveValues(sys.stdin.readline().strip())
for x in aList:
	for y in bList:
		if x == y:
			finalAns += 1
			bList.remove(y)
			break
finalAns += int(correctSeq / 2)
print(str(finalAns))


def chk(t):
	c = 0
	for i in range(len(t)):
		if t[i] == '(':
			c += 1
		else:
			c -= 1
		if c < 0:
			return -1
	return c

def chkrev(t):
	c = 0
	for i in range(len(t) - 1, -1, -1):
		if t[i] == ')':
			c += 1
		else:
			c -= 1
		if c < 0:
			return -1
	return c
N = int(input())
X = [0] * 500010
Y = [0] * 500010
Z = 0
ans = 0
for i in range(N):
	s = input()
	tmp = chk(s)
	if tmp > 0:
		if Y[tmp] > 0:
			Y[tmp] -= 1
			ans += 1
		else:
			X[tmp] += 1
	elif tmp == 0:
		if Z > 0:
			ans += 1
			Z -= 1
		else:
			Z += 1
	tmp = chkrev(s)
	if tmp > 0:
		if X[tmp] > 0:
			X[tmp] -= 1
			ans += 1
		else:
			Y[tmp] += 1
print(ans)


n = int(input())
a = []
for i in range(n):
	s = input()
	cur = 0
	u = len(s)
	j = 0
	while j < u and s[j] == ')':
		j += 1
		cur += 1
	count = 0
	for k in range(j, u):
		if s[k] == ')':
			count -= 1
		else:
			count += 1
		if count < 0:
			cur += 1
			count = 0
	if cur > 0 and count == 0:
		a.append(cur * -1)
	elif cur == 0:
		a.append(count)
a.sort()
(i, j) = (0, len(a) - 1)
ans = 0
while i < j:
	if a[i] + a[j] > 0:
		j -= 1
	elif a[i] + a[j] < 0:
		i += 1
	else:
		ans += 1
		i += 1
		j -= 1
print(ans)


def is_ok_first(a):
	balance = 0
	for item in a:
		if item == '(':
			balance += 1
		else:
			balance -= 1
			if balance < 0:
				return None
	return balance

def is_ok_second(a):
	balance = 0
	for item in a[::-1]:
		if item == '(':
			balance += 1
			if balance > 0:
				return None
		else:
			balance -= 1
	return balance
n = int(input())
a = []
for i in range(n):
	a.append(input())
only_start = {}
only_end = {}
even = 0
for item in a:
	f = is_ok_first(item)
	s = is_ok_second(item)
	if f != None:
		if f != 0:
			if f in only_start:
				only_start[f] += 1
			else:
				only_start[f] = 1
	if s != None:
		if s != 0:
			if s in only_end:
				only_end[s] += 1
			else:
				only_end[s] = 1
	if s == 0:
		even += 1
ans = 0
for key in only_start.keys():
	if -key in only_end.keys():
		f = only_start[key]
		s = only_end[-key]
		ans += min(f, s)
ans += even // 2
print(ans)


def f(s):
	(a, b) = (0, 0)
	for x in s:
		if x == ')':
			if b > 0:
				b -= 1
			else:
				a += 1
		else:
			b += 1
	return (a, b)
T = int(input())
k = 0
(seta, setb) = (list(), list())
for j in range(T):
	t = f(input())
	if t[0] == t[1] == 0:
		k += 1
	else:
		if t[0] == 0:
			if t[1] in seta:
				seta.remove(t[1])
				k += 2
			else:
				setb.append(t[1])
		if t[1] == 0:
			if t[0] in setb:
				setb.remove(t[0])
				k += 2
			else:
				seta.append(t[0])
print(k // 2)


import os, sys
from io import BytesIO, IOBase

def main():
	n = rint()
	a = rstr_2d(n)
	ma = max([len(x) for x in a])
	(pos, neg) = ([0] * (ma + 1), [0] * (ma + 1))
	for i in range(n):
		(su, po, ne) = (0, 1, 1)
		for j in a[i]:
			if j == '(':
				su += 1
			else:
				su -= 1
			if su < 0:
				po = 0
				break
		if po:
			pos[su] += 1
		su = 0
		for j in a[i][::-1]:
			if j == ')':
				su += 1
			else:
				su -= 1
			if su < 0:
				ne = 0
				break
		if ne:
			neg[su] += 1
	ans = pos[0] >> 1
	for i in range(1, ma + 1):
		ans += min(pos[i], neg[i])
	print(ans)

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
BUFSIZE = 8192
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
rstr = lambda : input().strip()
rstrs = lambda : [str(x) for x in input().split()]
rstr_2d = lambda n: [rstr() for _ in range(n)]
rint = lambda : int(input())
rints = lambda : [int(x) for x in input().split()]
rint_2d = lambda n: [rint() for _ in range(n)]
rints_2d = lambda n: [rints() for _ in range(n)]
ceil1 = lambda a, b: (a + b - 1) // b
main()