#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC target("avx")
using namespace std;
const long long maxn = 4e5 + 5;
const long long maxm = 1e3 + 5;
namespace IO {
const int SIZE = (1 << 20) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = obuf + SIZE - 1;
char _st[55];
int _qr = 0;
inline char gc() {
  return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
          (iS == iT ? EOF : *iS++) : *iS++);
}
inline void qread() {}
template <class T1, class... T2>
inline void qread(T1 &IEE, T2 &...ls) {
  T1 __ = 0, ___ = 1;
  char ch;
  while (!isdigit(ch = gc())) ___ = (ch == '-') ? -___ : ___;
  do {
    __ = (__ << 1) + (__ << 3) + (ch ^ 48);
  } while (isdigit(ch = gc()));
  __ *= ___;
  IEE = __;
  qread(ls...);
  return;
}
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
  return;
}
inline void putc_(char _x) {
  *oS++ = _x;
  if (oS == oT) flush();
}
inline void qwrite() {}
template <class T1, class... T2>
inline void qwrite(T1 IEE, T2... ls) {
  if (!IEE) putc_('0');
  if (IEE < 0) putc_('-'), IEE = -IEE;
  while (IEE) _st[++_qr] = IEE % 10 + '0', IEE /= 10;
  while (_qr) putc_(_st[_qr--]);
  qwrite(ls...);
  return;
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher;
}  // namespace IO
namespace rndom {
mt19937 mtrnd(std::chrono::system_clock::now().time_since_epoch().count());
long long rnd(long long x) { return mtrnd() % x; }
long long rndrg(long long l, long long r) { return l + rnd(r - l + 1); }
template <class T>
void rndshfl(T *pt, T *ed) {
  long long len = ed - pt;
  for (int i = 0; i < len; i++) swap(pt[i], pt[rnd(len)]);
  return;
}
}  // namespace rndom
using namespace IO;
using namespace rndom;
long long n;
int dp[1 << 20][2];
char s[20][maxn];
int f[maxn], mi[maxn];
int trs[maxn][20];
int cnt[maxn];
inline void upd(int &x, int y) { return x = x >= y ? x : y, void(); }
int main() {
  clock_t st = clock();
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  long long tot = 0;
  for (int i = 0; i < n; i++) {
    cin >> (s[i] + 1);
    int sum = 0;
    long long len = strlen(s[i] + 1);
    for (int j = 1; j <= len; j++) {
      sum += (s[i][j] == '(' ? 1 : -1);
      mi[i] = max(mi[i], -sum);
    }
    f[i] = sum;
    tot += len;
  }
  for (int i = 0; i < n; i++) {
    int len = strlen(s[i] + 1);
    int sum = (s[i][1] == '(' ? 1 : -1), now = 1;
    for (int j = 0; j <= tot - len; j++) {
      while (now <= len && sum + j >= 0) {
        if (sum <= 0) cnt[-sum]++;
        now++;
        sum += (s[i][now] == '(' ? 1 : -1);
      }
      trs[j][i] = cnt[j];
    }
    sum = 0;
    for (int j = 1; j <= len; j++) {
      sum += (s[i][j] == '(' ? 1 : -1);
      if (sum <= 0) cnt[-sum] = 0;
    }
  }
  memset(dp, -0x3f, sizeof(dp));
  dp[0][0] = 0;
  for (int i = 0; i < (1 << n); i++) {
    long long sum = 0;
    for (int j = 0; j < n; j++)
      if ((i >> j) & 1) sum += f[j];
    for (int j = 0; j < n; j++) {
      if ((i >> j) & 1) continue;
      upd(dp[i ^ (1 << j)][1], dp[i][1]);
      if (dp[i][0] >= 0)
        upd(dp[i ^ (1 << j)][sum < mi[j]], dp[i][0] + trs[sum][j]);
    }
  }
  cout << max(dp[(1 << n) - 1][0], dp[(1 << n) - 1][1]) << endl;
  return 0;
}

### Prompt

Your task is to create a cpp solution 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>
#pragma GCC optimize(2)
#pragma GCC target("avx")
using namespace std;
const long long maxn = 4e5 + 5;
const long long maxm = 1e3 + 5;
namespace IO {
const int SIZE = (1 << 20) + 1;
char ibuf[SIZE], *iS, *iT, obuf[SIZE], *oS = obuf, *oT = obuf + SIZE - 1;
char _st[55];
int _qr = 0;
inline char gc() {
  return (iS == iT ? iT = (iS = ibuf) + fread(ibuf, 1, SIZE, stdin),
          (iS == iT ? EOF : *iS++) : *iS++);
}
inline void qread() {}
template <class T1, class... T2>
inline void qread(T1 &IEE, T2 &...ls) {
  T1 __ = 0, ___ = 1;
  char ch;
  while (!isdigit(ch = gc())) ___ = (ch == '-') ? -___ : ___;
  do {
    __ = (__ << 1) + (__ << 3) + (ch ^ 48);
  } while (isdigit(ch = gc()));
  __ *= ___;
  IEE = __;
  qread(ls...);
  return;
}
inline void flush() {
  fwrite(obuf, 1, oS - obuf, stdout);
  oS = obuf;
  return;
}
inline void putc_(char _x) {
  *oS++ = _x;
  if (oS == oT) flush();
}
inline void qwrite() {}
template <class T1, class... T2>
inline void qwrite(T1 IEE, T2... ls) {
  if (!IEE) putc_('0');
  if (IEE < 0) putc_('-'), IEE = -IEE;
  while (IEE) _st[++_qr] = IEE % 10 + '0', IEE /= 10;
  while (_qr) putc_(_st[_qr--]);
  qwrite(ls...);
  return;
}
struct Flusher_ {
  ~Flusher_() { flush(); }
} io_flusher;
}  // namespace IO
namespace rndom {
mt19937 mtrnd(std::chrono::system_clock::now().time_since_epoch().count());
long long rnd(long long x) { return mtrnd() % x; }
long long rndrg(long long l, long long r) { return l + rnd(r - l + 1); }
template <class T>
void rndshfl(T *pt, T *ed) {
  long long len = ed - pt;
  for (int i = 0; i < len; i++) swap(pt[i], pt[rnd(len)]);
  return;
}
}  // namespace rndom
using namespace IO;
using namespace rndom;
long long n;
int dp[1 << 20][2];
char s[20][maxn];
int f[maxn], mi[maxn];
int trs[maxn][20];
int cnt[maxn];
inline void upd(int &x, int y) { return x = x >= y ? x : y, void(); }
int main() {
  clock_t st = clock();
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  cin >> n;
  long long tot = 0;
  for (int i = 0; i < n; i++) {
    cin >> (s[i] + 1);
    int sum = 0;
    long long len = strlen(s[i] + 1);
    for (int j = 1; j <= len; j++) {
      sum += (s[i][j] == '(' ? 1 : -1);
      mi[i] = max(mi[i], -sum);
    }
    f[i] = sum;
    tot += len;
  }
  for (int i = 0; i < n; i++) {
    int len = strlen(s[i] + 1);
    int sum = (s[i][1] == '(' ? 1 : -1), now = 1;
    for (int j = 0; j <= tot - len; j++) {
      while (now <= len && sum + j >= 0) {
        if (sum <= 0) cnt[-sum]++;
        now++;
        sum += (s[i][now] == '(' ? 1 : -1);
      }
      trs[j][i] = cnt[j];
    }
    sum = 0;
    for (int j = 1; j <= len; j++) {
      sum += (s[i][j] == '(' ? 1 : -1);
      if (sum <= 0) cnt[-sum] = 0;
    }
  }
  memset(dp, -0x3f, sizeof(dp));
  dp[0][0] = 0;
  for (int i = 0; i < (1 << n); i++) {
    long long sum = 0;
    for (int j = 0; j < n; j++)
      if ((i >> j) & 1) sum += f[j];
    for (int j = 0; j < n; j++) {
      if ((i >> j) & 1) continue;
      upd(dp[i ^ (1 << j)][1], dp[i][1]);
      if (dp[i][0] >= 0)
        upd(dp[i ^ (1 << j)][sum < mi[j]], dp[i][0] + trs[sum][j]);
    }
  }
  cout << max(dp[(1 << n) - 1][0], dp[(1 << n) - 1][1]) << endl;
  return 0;
}

```