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.
1
)(((((()((())(((((((
 1
)()())((()))((()((()
 10
((((((((((((((((()))))))))))))))))
(((((((((((((((())))))))))))))))
((((((((((((((((((((()))))))))))))))))))))
(((((((((((((((((((((())))))))))))))))))))))
()()()()()()()()()()()()()()()()()()()()
()()()()()()()()()()()()()()()()()()()()()()()()()()
(((((((((((((((((())))))))))))))))))
()()()()()()()()()()()()()()()()()()()
()()()()()()()()()()()()()()()()()()
()()()()()()()()()()()()()()()()()()()()()()()
 20
)
(
)
)
)
)
)
(
(
)
)
)
)
(
)
)
)
)
(
)
 6
()()()()()
()()()()
()
((((()))))
((()))
()()
 1
((((((((((((((((((((
 10
((((((((((((((((((((((((()))))))))))))))))))))))))
()()()()()()()()()()()()()()()()()()()
(((((((((((((((((())))))))))))))))))
()()()()()()()()()()()()()()()()()()()()()()
((((((((((((((((((()))))))))))))))))))
((((((((((((((((((((((()))))))))))))))))))))))
()()()()()()()()()()()()()()()()()()()
((((((((((((((()))))))))))))))
()()()()()()()()()()()()()()()()()()()()()()()()
()()()()()()()()()()()()()()()()
 2
))())))((()
()((((((()))))))(()
 20
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
 20
(
(
)
(
(
)
(
(
(
(
(
(
)
)
(
(
(
(
(
)
 10
()()
(())
()()
()()
(())
(((())))
()
(())
()()
()
 1
))))))))))))))))))))
 6
(((())))
(((())))
()()()
(())
()()()()()
()()
 10
)
)
))
))
))
))
))
))
)))
)))
 10
)()
()
)
)
)
)(
)))
)(
(((
))
 20
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
 10
))
()(
(
()
()
((((
(
(
(((
(
 10
()
()()()()
(())
((()))
(())
()()
(())
()()
()
()
 10
())
()
)
)))
))
()
)
))
)))
)
 1
))))))()))())(()))))
 10
((
(((
(
(((
((((
((
(
(
(
((
 20
)
(
(
)
)
(
)
(
(
(
)
)
)
)
(
)
(
(
)
(

0
 0
 111
 5
 14
 0
 105
 3
 0
 5
 14
 0
 13
 0
 5
 0
 4
 15
 3
 0
 0
 10

#include <bits/stdc++.h>
using namespace std;
const int N = 4e5 + 6;
int n, f[1 << 20];
struct STR {
  char s[N];
  int pos[N], len, nx[N], tp[N], rest[N], step[N];
  int k;
  void init() {
    len = strlen(s + 1);
    static int sta[N];
    int top = 0;
    for (int i = 1; i <= len; ++i)
      if (s[i] == '(') {
        sta[++top] = i;
      } else {
        if (top && s[sta[top]] == '(')
          nx[sta[top--]] = i + 1;
        else {
          sta[++top] = i;
          if (!pos[top]) pos[top] = i;
        }
      }
    top = 0;
    for (int i = len; i; --i) {
      if (s[i] == '(') {
        if (top && s[sta[top]] == ')')
          --top;
        else
          sta[++top] = i;
      } else
        sta[++top] = s[i];
      if (!top || s[sta[top]] == '(')
        rest[i] = top;
      else
        rest[i] = -1;
    }
    tp[len + 1] = len + 1;
    for (int i = len; i; --i) {
      if (nx[i]) {
        tp[i] = tp[nx[i]];
        step[i] = step[nx[i]] + 1;
      } else {
        tp[i] = i;
        step[i] = 0;
      }
    }
    for (int i = 1; i <= len; ++i)
      if (s[i] == '(')
        ++k;
      else
        --k;
  }
} a[21];
int ans;
int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  cin >> n;
  for (int i = 0; i < n; ++i) cin >> (a[i].s + 1);
  for (int i = 0; i < n; ++i) a[i].init();
  memset(f, -1, sizeof f);
  for (int i = 0; i < n; ++i) {
    int p = a[i].tp[1], Step = a[i].step[1];
    ans = max(ans, Step);
    if (a[i].rest[p] != -1) f[1 << i] = Step;
  }
  for (int c = 1; c < n; ++c)
    for (int S = 1; S < 1 << n; ++S)
      if (__builtin_popcount(S) == c && f[S] != -1) {
        int t = 0;
        for (int i = 0; i < n; ++i)
          if (S >> i & 1) t += a[i].k;
        if (t < 0) continue;
        for (int j = 0; j < n; ++j)
          if (!(S >> j & 1)) {
            if ((t <= a[j].len && a[j].pos[t] != 0) || t == 0) {
              int p = (t == 0) ? 1 : a[j].pos[t] + 1;
              int val = f[S] + a[j].step[p] + !!t;
              p = a[j].tp[p];
              ans = max(ans, val);
              if (a[j].rest[p] != -1) f[S | 1 << j] = max(f[S | 1 << j], val);
            } else
              f[S | 1 << j] = max(f[S | 1 << j], f[S]);
          }
      }
  cout << ans << '\n';
  return 0;
}
