description: 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.
solution: #include <bits/stdc++.h>
  using namespace std;
  const int MOD = 1000000007;
  const int inf = 0x3f3f3f3f;
  const int N = 410000;
  const int M = 20;
  template <typename T>
  inline bool scan_d(T& ret) {
    char c;
    int sgn;
    if (c = getchar(), c == EOF) return 0;
    while (c != '-' && (c < '0' || c > '9')) {
      if ((c = getchar()) == EOF) return 0;
    }
    sgn = (c == '-') ? -1 : 1;
    ret = (c == '-') ? 0 : (c - '0');
    while (c = getchar(), c >= '0' && c <= '9') ret = ret * 10 + (c - '0');
    ret *= sgn;
    return 1;
  }
  template <typename T>
  void print(T x) {
    static char s[33], *s1;
    s1 = s;
    if (!x) *s1++ = '0';
    if (x < 0) putchar('-'), x = -x;
    while (x) *s1++ = (x % 10 + '0'), x /= 10;
    while (s1-- != s) putchar(*s1);
  }
  template <typename T>
  void println(T x) {
    print(x);
    putchar('\n');
  }
  struct TPoint {
    string s;
    int x, y;
    map<int, int> v;
    void solve() {
      x = y;
      v.clear();
      int n = s.length();
      vector<int> a(n + 2, -1);
      vector<int> b(n + 2, -1);
      a[0] = b[0] = 0;
      a[n + 1] = b[n + 1] = 0;
      stack<char> s1, s2, s3;
      for (int i = (0); i < (n); ++i) {
        if (!s1.empty() && s1.top() == '(' && s[i] == ')')
          s1.pop();
        else
          s1.push(s[i]);
        if (s1.empty() || s1.top() == ')') a[i + 1] = s1.size();
        if (s1.empty() || s1.top() == ')') v[s1.size()]++;
      }
      for (int i = (n)-1; i >= (0); --i) {
        if (!s2.empty() && s2.top() == ')' && s[i] == '(')
          s2.pop();
        else
          s2.push(s[i]);
        if (s2.empty() || s2.top() == '(') b[i + 1] = s2.size();
      }
      for (int i = (0); i < (n + 1); ++i) {
        if (a[i] != -1 && b[i + 1] != -1) {
          x = a[i], y = b[i + 1];
          break;
        }
      }
    }
  };
  TPoint a[M];
  int n, dp[(1ll << (M))], b[(1ll << (M))];
  char sread[N];
  void fmain() {
    scan_d(n);
    for (int i = (0); i < (n); ++i) {
      scanf("%s", sread);
      a[i].s.assign(sread);
      a[i].solve();
    }
    int res = 0;
    for (int cur = (1); cur < ((1ll << (n))); ++cur) {
      dp[cur] = -1;
      for (int i = (0); i < (n); ++i)
        if (cur & (1ll << (i))) {
          int las = cur ^ (1ll << (i));
          if (dp[las] == -1) continue;
          if (a[i].x > b[las]) {
            res = max(res, dp[las] + a[i].v[b[las]]);
            continue;
          }
          int val = dp[las];
          int leave = b[las] - a[i].x;
          if (leave == 0) val += a[i].v[b[las]];
          if (dp[cur] <= val) {
            dp[cur] = val;
            b[cur] = leave + a[i].y;
          }
        }
    }
    res = max(res, dp[(1ll << (n)) - 1]);
    println(res);
  }
  int main() {
    char ch;
    while (scanf(" %c", &ch) != EOF) {
      ungetc(ch, stdin);
      fmain();
    }
    return 0;
  }
  