#include <bits/stdc++.h>
using namespace std;
template <class a, class b>
ostream& operator<<(ostream& os, const pair<a, b>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "[";
  if (!v.size())
    os << "]";
  else
    for (int i = 0; i < v.size(); ++i) os << v[i] << ",]"[i == v.size() - 1];
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& s) {
  os << "{";
  if (!s.size())
    os << "}";
  else
    for (auto x : s) os << x << ",}"[x == *s.rbegin()];
  return os;
}
void printr(ostream& os) { os << '\n'; }
template <class T, class... Args>
void printr(ostream& os, const T& t, const Args&... args) {
  os << t;
  if (sizeof...(args)) os << " ";
  printr(os, args...);
}
template <class T>
void read(T& x) {
  cin >> x;
}
template <class T, class... Args>
void read(T& t, Args&... args) {
  read(t), read(args...);
}
template <class T>
void readarray(T* A, int n) {
  for (__typeof(0) i = (0), _end = (n), _step = 1 - 2 * ((0) > (n)); i != _end;
       i += _step)
    read(A[i]);
}
void dbgr(ostream& os) { os << endl; }
template <class T, class... Args>
void dbgr(ostream& os, const T& t, const Args&... args) {
  os << t;
  if (sizeof...(args)) os << ", ";
  dbgr(os, args...);
}
long long randll(long long a, long long b) {
  uniform_int_distribution<int> u(a, b);
  static mt19937 e(time(0));
  return u(e);
}
long long pw(long long a, long long k = 998244353 - 2) {
  long long ans = 1;
  for (a %= 998244353; k; k >>= 1) {
    if (k & 1) ans = ans * a % 998244353;
    a = a * a % 998244353;
  }
  return ans;
}
int n;
int a[21], b[21];
vector<int> con[21];
int stk[2000050], tp;
int sum[2000050], dp[2000050];
int getcon(int i, int j) {
  if (j < con[i].size()) return con[i][j];
  return 0;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (__typeof(0) i = (0), _end = (n), _step = 1 - 2 * ((0) > (n)); i != _end;
       i += _step) {
    string s;
    cin >> s;
    con[i].resize(s.size() + 1);
    tp = 0;
    for (__typeof(0) j = (0), _end = (s.size()),
                     _step = 1 - 2 * ((0) > (s.size()));
         j != _end; j += _step) {
      if (s[j] == ')' && tp && s[stk[tp]] == '(')
        --tp;
      else
        stk[++tp] = j;
      if (tp && s[stk[tp]] == '(') continue;
      ++con[i][tp];
    }
    for (; tp; --tp) {
      if (s[stk[tp]] == '(')
        ++b[i];
      else
        ++a[i];
    }
  }
  memset(dp, 0xc0, sizeof(dp));
  dp[0] = sum[0] = 0;
  int ans = 0;
  for (int s = 0; s < (1 << n); ++s) {
    for (int i = 0; i < n; ++i) {
      if (~s >> i & 1) continue;
      int t = s ^ (1 << i);
      sum[s] = sum[t] - a[i] + b[i];
      if (sum[t] < a[i]) continue;
      dp[s] = max(dp[s], dp[t] + getcon(i, sum[t]));
    }
    for (int i = 0; i < n; ++i)
      if (~s >> i & 1) {
        ans = max(ans, dp[s] + getcon(i, sum[s]));
      }
  }
  cout << ans << endl;
  return 0;
}

### Prompt

Please create a solution in Cpp to the following problem:

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.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class a, class b>
ostream& operator<<(ostream& os, const pair<a, b>& p) {
  os << "(" << p.first << "," << p.second << ")";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& v) {
  os << "[";
  if (!v.size())
    os << "]";
  else
    for (int i = 0; i < v.size(); ++i) os << v[i] << ",]"[i == v.size() - 1];
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& s) {
  os << "{";
  if (!s.size())
    os << "}";
  else
    for (auto x : s) os << x << ",}"[x == *s.rbegin()];
  return os;
}
void printr(ostream& os) { os << '\n'; }
template <class T, class... Args>
void printr(ostream& os, const T& t, const Args&... args) {
  os << t;
  if (sizeof...(args)) os << " ";
  printr(os, args...);
}
template <class T>
void read(T& x) {
  cin >> x;
}
template <class T, class... Args>
void read(T& t, Args&... args) {
  read(t), read(args...);
}
template <class T>
void readarray(T* A, int n) {
  for (__typeof(0) i = (0), _end = (n), _step = 1 - 2 * ((0) > (n)); i != _end;
       i += _step)
    read(A[i]);
}
void dbgr(ostream& os) { os << endl; }
template <class T, class... Args>
void dbgr(ostream& os, const T& t, const Args&... args) {
  os << t;
  if (sizeof...(args)) os << ", ";
  dbgr(os, args...);
}
long long randll(long long a, long long b) {
  uniform_int_distribution<int> u(a, b);
  static mt19937 e(time(0));
  return u(e);
}
long long pw(long long a, long long k = 998244353 - 2) {
  long long ans = 1;
  for (a %= 998244353; k; k >>= 1) {
    if (k & 1) ans = ans * a % 998244353;
    a = a * a % 998244353;
  }
  return ans;
}
int n;
int a[21], b[21];
vector<int> con[21];
int stk[2000050], tp;
int sum[2000050], dp[2000050];
int getcon(int i, int j) {
  if (j < con[i].size()) return con[i][j];
  return 0;
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  cin >> n;
  for (__typeof(0) i = (0), _end = (n), _step = 1 - 2 * ((0) > (n)); i != _end;
       i += _step) {
    string s;
    cin >> s;
    con[i].resize(s.size() + 1);
    tp = 0;
    for (__typeof(0) j = (0), _end = (s.size()),
                     _step = 1 - 2 * ((0) > (s.size()));
         j != _end; j += _step) {
      if (s[j] == ')' && tp && s[stk[tp]] == '(')
        --tp;
      else
        stk[++tp] = j;
      if (tp && s[stk[tp]] == '(') continue;
      ++con[i][tp];
    }
    for (; tp; --tp) {
      if (s[stk[tp]] == '(')
        ++b[i];
      else
        ++a[i];
    }
  }
  memset(dp, 0xc0, sizeof(dp));
  dp[0] = sum[0] = 0;
  int ans = 0;
  for (int s = 0; s < (1 << n); ++s) {
    for (int i = 0; i < n; ++i) {
      if (~s >> i & 1) continue;
      int t = s ^ (1 << i);
      sum[s] = sum[t] - a[i] + b[i];
      if (sum[t] < a[i]) continue;
      dp[s] = max(dp[s], dp[t] + getcon(i, sum[t]));
    }
    for (int i = 0; i < n; ++i)
      if (~s >> i & 1) {
        ans = max(ans, dp[s] + getcon(i, sum[s]));
      }
  }
  cout << ans << endl;
  return 0;
}

```