A bracket sequence is a string containing only characters "(" and ")". A regular bracket sequence (or, shortly, an RBS) is a bracket sequence that can be transformed into a correct arithmetic expression by inserting characters "1" and "+" between the original characters of the sequence. For example:

  * bracket sequences "()()" and "(())" are regular (the resulting expressions are: "(1)+(1)" and "((1+1)+1)"); 
  * bracket sequences ")(", "(" and ")" are not. 



Let's denote the concatenation of two strings x and y as x+y. For example, "()()" + ")(" = "()())(".

You are given n bracket sequences s_1, s_2, ..., s_n. You can rearrange them in any order (you can rearrange only the strings themselves, but not the characters in them).

Your task is to rearrange the strings in such a way that the string s_1 + s_2 + ... + s_n has as many non-empty prefixes that are RBS as possible.

Input

The first line contains a single integer n (1 ≤ n ≤ 20).

Then n lines follow, the i-th of them contains s_i — a bracket sequence (a string consisting of characters "(" and/or ")". All sequences s_i are non-empty, their total length does not exceed 4 ⋅ 10^5.

Output

Print one integer — the maximum number of non-empty prefixes that are RBS for the string s_1 + s_2 + ... + s_n, if the strings s_1, s_2, ..., s_n can be rearranged arbitrarily.

Examples

Input


2
(
)


Output


1


Input


4
()()())
(
(
)


Output


4


Input


1
(())


Output


1


Input


1
)(()


Output


0

Note

In the first example, you can concatenate the strings as follows: "(" + ")" = "()", the resulting string will have one prefix, that is an RBS: "()".

In the second example, you can concatenate the strings as follows: "(" + ")" + "()()())" + "(" = "()()()())(", the resulting string will have four prefixes that are RBS: "()", "()()", "()()()", "()()()()".

The third and the fourth examples contain only one string each, so the order is fixed.

Source: codeforces | Difficulty: VERY_HARD
Tags: Bit manipulation

Sorting

Complete search

Dynamic programming

Data structures


Solutions:
import sys
from sys import stdin
n = int(stdin.readline())
s = [list(stdin.readline()[:-1]) for i in range(n)]
smin = [0] * n
smnum = [0] * n
h = [0] * n
cnts = [{} for i in range(n)]
for i in range(n):
	ts = s[i]
	nmin = 0
	nh = 0
	for c in ts:
		if c == '(':
			nh += 1
		else:
			nh -= 1
		if smin[i] > nh:
			smin[i] = nh
			smnum[i] = 0
		if smin[i] == nh:
			smnum[i] += 1
		if nh == smin[i]:
			if nh not in cnts[i]:
				cnts[i][nh] = 0
			cnts[i][nh] += 1
	h[i] = nh
dp = [float('-inf')] * 2 ** n
dp[0] = 0
ans = 0
for i in range(2 ** n):
	nh = 0
	for j in range(n):
		if 2 ** j & i > 0:
			nh += h[j]
	for j in range(n):
		if 2 ** j & i == 0 and nh + smin[j] >= 0:
			if nh + smin[j] == 0:
				dp[2 ** j | i] = max(dp[2 ** j | i], dp[i] + smnum[j])
			else:
				dp[2 ** j | i] = max(dp[2 ** j | i], dp[i])
		elif 2 ** j & i == 0 and -1 * nh in cnts[j]:
			ans = max(ans, dp[i] + cnts[j][-1 * nh])
ans = max(ans, max(dp))
print(ans)


from sys import stdin, stdout
import sys
import heapq
from collections import defaultdict
import math
import bisect
import io, os
import copy
import itertools

def ncr(n, r, p):
	num = den = 1
	for i in range(r):
		num = num * (n - i) % p
		den = den * (i + 1) % p
	return num * pow(den, p - 2, p) % p

def kbits(n, k):
	result = []
	for bits in itertools.combinations(range(n), k):
		s = ['0'] * n
		for bit in bits:
			s[bit] = '1'
		result.append(''.join(s))
	return result

def main():
	n = int(stdin.readline())
	cnt = [[] for _ in range(n)]
	L = []
	R = []
	for i in range(n):
		(l, r) = (0, 0)
		st = stdin.readline().strip()
		for _ in range(len(st) + 1):
			cnt[i].append(0)
		for x in st:
			if x == ')':
				if r > 0:
					r -= 1
					if r == 0:
						cnt[i][l] += 1
				else:
					l += 1
			else:
				r += 1
		L.append(l)
		R.append(r)
	dp = [-1] * pow(2, n)
	dp[0] = 0
	dp_mx = [0] * pow(2, n)
	ans = 0
	for c in range(n):
		if c == 0:
			perm = ['0' * n]
		else:
			perm = kbits(n, c)
		for p in perm:
			num = int(p, 2)
			if dp[num] == -1:
				continue
			k = 1
			for (i, s) in enumerate(reversed(p)):
				if s == '0':
					bal = dp[num]
					sm = dp_mx[num]
					if bal - L[i] > 0:
						bal -= L[i] - R[i]
						dp[num + k] = bal
						dp_mx[num + k] = max(sm, dp_mx[num + k])
						ans = max(dp_mx[num + k], ans)
					elif bal - L[i] == 0:
						if bal > 0:
							sm += 1
						sm += cnt[i][L[i]]
						dp[num + k] = R[i]
						dp_mx[num + k] = max(sm, dp_mx[num + k])
						ans = max(dp_mx[num + k], ans)
					else:
						sm += cnt[i][bal]
						if bal > 0:
							sm += 1
						ans = max(sm, ans)
				k *= 2
	if ans == 3 and n == 5:
		print(L)
		print(R)
		print(dp_mx)
	stdout.write(str(ans) + '\n')
main()


import sys
inp = sys.stdin.readline

def solve():
	n = int(inp())
	a = [[0] for i in range(n)]
	mb = [0] * (1 << n)
	for i in range(n):
		s = inp().strip()
		m = 0
		b = 0
		for c in s:
			if c == '(':
				b += 1
			else:
				b -= 1
				if b <= 0:
					if m > b:
						m = b
						a[i].append(1)
					elif m == b:
						a[i][-1] += 1
		mb[1 << i] = b
	dp = [None] * (1 << n)
	dp[0] = 0
	ans = 0
	for i in range(1, 1 << n):
		j = i & i - 1
		if j:
			mb[i] = mb[i - j] + mb[j]
		nd = None
		for j in range(n):
			if i >> j & 1:
				d = dp[i - (1 << j)]
				if d is not None:
					bb = mb[i - (1 << j)]
					m = len(a[j]) - 1
					if bb - m < 0:
						ans = max(ans, a[j][bb] + d)
					elif bb - m == 0:
						if nd is None:
							nd = a[j][-1] + d
						else:
							nd = max(nd, a[j][-1] + d)
					elif nd is None:
						nd = d
					else:
						nd = max(nd, d)
		if nd is not None:
			ans = max(ans, nd)
		dp[i] = nd
	print(ans)

def main():
	solve()
main()


import io, os
import bisect
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def getnext(state, pre, infor, dic, dp):
	if state in dp:
		return dp[state]
	output = 0
	for i in range(len(infor)):
		if state & 1 << i > 0:
			continue
		if pre[state] + infor[i][1] < 0:
			firstappear = dic[i][-pre[state] - 1][0]
			temp = 0
			if -pre[state] in dic[i]:
				temp = bisect.bisect_left(dic[i][-pre[state]], firstappear)
			output = max(output, temp)
			continue
		base = 0
		if -pre[state] in dic[i]:
			base = len(dic[i][-pre[state]])
		temp = base + getnext(state + (1 << i), pre, infor, dic, dp)
		output = max(output, temp)
	dp[state] = output
	return output

def main(t):
	n = int(input())
	grid = []
	infor = []
	dic = [{} for _ in range(n)]
	pre = [0 for _ in range(1 << n)]
	for k in range(n):
		curr = 0
		minimum = 1
		s = input()
		for i in range(len(s)):
			if s[i] == ord('('):
				curr += 1
			elif s[i] == ord(')'):
				curr -= 1
			else:
				break
			if curr < minimum:
				minimum = curr
			if curr not in dic[k]:
				dic[k][curr] = []
			dic[k][curr].append(i)
		infor.append([curr, minimum, len(dic[k][minimum])])
	for state in range(1 << n):
		s = bin(state)[2:][::-1]
		s += '0' * (n - len(s))
		for i in range(n):
			if s[i] == '1':
				pre[state] += infor[i][0]
	dp = {}
	ans = getnext(0, pre, infor, dic, dp)
	print(ans)
T = 1
t = 1
while t <= T:
	main(t)
	t += 1


def solve():
	n = int(input())
	a = [[0] for i in range(n)]
	mb = [0] * (1 << n)
	for i in range(n):
		s = input().strip()
		m = 0
		b = 0
		for c in s:
			if c == '(':
				b += 1
			else:
				b -= 1
				if b <= 0:
					if m > b:
						m = b
						a[i].append(1)
					elif m == b:
						a[i][-1] += 1
		mb[1 << i] = b
	dp = [-1000000000] * (1 << n)
	dp[0] = 0
	ans = 0
	for i in range(1, 1 << n):
		j = i & i - 1
		if j:
			mb[i] = mb[i - j] + mb[j]
		nd = -1000000000
		for j in range(n):
			if i >> j & 1:
				d = dp[i - (1 << j)]
				if d >= 0:
					bb = mb[i - (1 << j)]
					m = len(a[j]) - 1
					if bb - m < 0:
						ans = max(ans, a[j][bb] + d)
					else:
						nd = max(nd, (a[j][-1] if bb - m == 0 else 0) + d)
		ans = max(ans, nd)
		dp[i] = nd
	print(ans)
solve()