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 INF = int(1e9);
  const int N = 20;
  const int M = (1 << N);
  struct BracketSeqn {
    int balance;
    int lowestBalance;
    vector<int> queryAns;
    pair<int, bool> go(int x, bool f) {
      if (f)
        return make_pair(0, true);
      else
        return make_pair(x < queryAns.size() ? queryAns[x] : 0,
                         x + lowestBalance < 0);
    }
    BracketSeqn(){};
    BracketSeqn(string s) {
      vector<int> bal;
      int cur = 0;
      int n = s.size();
      for (auto x : s) {
        if (x == '(')
          cur++;
        else
          cur--;
        bal.push_back(cur);
      }
      balance = bal.back();
      lowestBalance = min(0, *min_element(bal.begin(), bal.end()));
      vector<vector<int>> negPos(-lowestBalance + 1);
      for (int i = 0; i < n; i++) {
        if (bal[i] > 0) continue;
        negPos[-bal[i]].push_back(i);
      }
      queryAns.resize(-lowestBalance + 1);
      for (int i = 0; i < queryAns.size(); i++) {
        int lastPos = int(1e9);
        if (i != -lowestBalance) lastPos = negPos[i + 1][0];
        queryAns[i] = lower_bound(negPos[i].begin(), negPos[i].end(), lastPos) -
                      negPos[i].begin();
      }
    };
  };
  int dp[M][2];
  char buf[M];
  int total_bal[M];
  int main() {
    int n;
    scanf("%d", &n);
    vector<BracketSeqn> bs;
    for (int i = 0; i < n; i++) {
      scanf("%s", buf);
      string s = buf;
      bs.push_back(BracketSeqn(s));
    }
    for (int i = 0; i < (1 << n); i++)
      for (int j = 0; j < n; j++)
        if (i & (1 << j)) total_bal[i] += bs[j].balance;
    for (int i = 0; i < (1 << n); i++)
      for (int j = 0; j < 2; j++) dp[i][j] = -int(1e9);
    dp[0][0] = 0;
    for (int i = 0; i < (1 << n); i++)
      for (int f = 0; f < 2; f++) {
        if (dp[i][f] < 0) continue;
        for (int k = 0; k < n; k++) {
          if (i & (1 << k)) continue;
          pair<int, bool> res = bs[k].go(total_bal[i], f);
          dp[i ^ (1 << k)][res.second] =
              max(dp[i ^ (1 << k)][res.second], dp[i][f] + res.first);
        }
      }
    printf("%d\n", max(dp[(1 << n) - 1][0], dp[(1 << n) - 1][1]));
  }
  