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 long long mod = 1e9 + 7;
  long long inv(long long i) {
    if (i == 1) return 1;
    return (mod - ((mod / i) * inv(mod % i)) % mod) % mod;
  }
  long long mod_mul(long long a, long long b) {
    a = a % mod;
    b = b % mod;
    return (((a * b) % mod) + mod) % mod;
  }
  long long mod_add(long long a, long long b) {
    a = a % mod;
    b = b % mod;
    return (((a + b) % mod) + mod) % mod;
  }
  long long gcd(long long a, long long b) {
    if (b == 0) return a;
    return gcd(b, a % b);
  }
  long long ceil_div(long long a, long long b) {
    return a % b == 0 ? a / b : a / b + 1;
  }
  long long pwr(long long a, long long b) {
    a %= mod;
    long long res = 1;
    while (b > 0) {
      if (b & 1) res = res * a % mod;
      a = a * a % mod;
      b >>= 1;
    }
    return res;
  }
  struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
      x += 0x9e3779b97f4a7c15;
      x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
      x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
      return x ^ (x >> 31);
    }
    size_t operator()(uint64_t x) const {
      static const uint64_t FIXED_RANDOM =
          chrono::steady_clock::now().time_since_epoch().count();
      return splitmix64(x + FIXED_RANDOM);
    }
  };
  int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    long long t, n, i, j, ans, temp, sum;
    string sans;
    t = 1;
    while (t--) {
      sans = "NO";
      ans = temp = sum = 0;
      cin >> n;
      vector<string> a(n);
      vector<unordered_map<long long, long long, custom_hash>> cnt(n);
      vector<long long> mn(n, 1000000000000000005);
      vector<long long> tot(n, 0);
      for (i = 0; i <= n - 1; i++) {
        cin >> a[i];
        long long sz = a[i].size();
        sum = 0;
        for (j = 0; j <= sz - 1; j++) {
          if (a[i][j] == '(')
            sum++;
          else
            sum--;
          mn[i] = min(mn[i], sum);
          if (sum == mn[i]) {
            cnt[i][mn[i]]++;
          }
        }
        tot[i] = sum;
      }
      vector<long long> dp((1 << n), -1000000000000000005);
      ans = 0;
      dp[0] = 0;
      for (i = 0; i < (1 << n); i++) {
        long long balance = 0;
        for (j = 0; j <= n - 1; j++) {
          if (i & (1 << j)) balance += tot[j];
        }
        if (balance >= 0) {
          for (j = 0; j < n; j++) {
            if (!(i & (1 << j))) {
              long long i2 = i | (1 << j);
              if (balance > -mn[j]) {
                dp[i2] = max(dp[i2], dp[i]);
              } else if (balance == -mn[j]) {
                dp[i2] = max(dp[i2], dp[i] + cnt[j][mn[j]]);
                ans = max(ans, dp[i2]);
              } else {
                ans = max(ans, dp[i] + cnt[j][-balance]);
              }
            }
          }
        }
      }
      cout << ans;
    }
    return 0;
  }
  