human
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.
Using python3 can you solve the prior task?
 ... What is a Python code to print one integer — the maximum number of non-empty prefixes that are RBS for the string s_1 + s_2 +?
assistant
#Here is Python code to print one integer — the maximum number of non-empty prefixes that are RBS for the string s_1 + s_2 + .

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

# for interactive problem
# n = int(stdin.readline())
# print(x, flush=True)

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

def ncr(n, r, p):
    # initialize numerator
    # and denominator
    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

#input = sys.stdin.buffer.readline

# ffi = FFI()
# ffi.cdef(
#     """
#     typedef struct {
#         long long suf;
#         long long pre;
#         long long maxi;
#         bool is_plus;
#         long long lowest;
#         long long sum;
#         int length;
#     } node_t;
#     """
# )
#
# MX = 2 << ((2 * 10 ** 5) - 1).bit_length()
# data = ffi.new("node_t[]", MX + 3)
# data[MX] = (0, 0, 0, True, 0, 0, 0)
# id_node = data[MX]
# res_left = MX + 1
# res_right = MX + 2
#
# def combine(a, b):
#     if a.length == 0:
#         return b
#     if b.length == 0:
#         return a
#
#     length = a.length + b.length
#     if a.is_plus:
#         pre = a.sum + b.pre
#     else:
#         pre = a.pre
#     if b.is_plus:
#         suf = a.suf + b.sum
#     else:
#         suf = b.suf
#     is_plus = a.is_plus and b.is_plus
#     sum = a.sum + b.sum
#     maxi = max(a.maxi, b.maxi, a.suf + b.pre)
#     lowest = min(a.lowest, a.sum + b.lowest)
#     return (suf, pre, maxi, is_plus, lowest, sum, length)
#
# def mapValue(x):
#     return (max(x, 0), max(x, 0), max(x, 0), (x >= 0), x, x, 1)
#
# class SegmentTree:
#     def __init__(self, N, A):
#         self._len = N
#         self._size = _size = 1 << (self._len - 1).bit_length()
#         for i in range(2 * _size):
#             data[i] = id_node
#         for i, x in enumerate(A):
#             data[_size + i] = mapValue(x)
#         for i in reversed(range(_size)):
#             data[i] = combine(data[i + i],...