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>
  std::vector<std::string> v;
  int n;
  const int MAX_N = 20;
  int sum[MAX_N + 3];
  int min[MAX_N + 3];
  const int MAX_MASK = (1 << 20);
  int total_sum[MAX_MASK + 3];
  int dp[MAX_MASK + 5];
  const int MAX_M = 4e5;
  int cnt_pos[MAX_N + 3][2 * MAX_M + 3];
  bool is_bit(int mask, int pos) { return (mask & (1 << pos)) != 0; }
  int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(NULL);
    std::cin >> n;
    for (int i = 1; i <= n; i++) {
      std::string s;
      std::cin >> s;
      v.push_back(s);
    }
    for (int i = 0; i < n; i++) {
      int S = 0;
      int m = INT_MAX;
      for (auto c : v[i]) {
        if (c == ')')
          S--;
        else
          S++;
        m = std::min(m, S);
        if (S == m) cnt_pos[i][MAX_M + S]++;
      }
      sum[i] = S, min[i] = m;
    }
    for (int mask = 0; mask < (1 << n); mask++) {
      total_sum[mask] = 0;
      dp[mask] = -1;
      for (int i = 0; i < n; i++)
        if (is_bit(mask, i)) total_sum[mask] += sum[i];
    }
    dp[0] = 0;
    int res = 0;
    for (int mask = 0; mask < (1 << n); mask++) {
      if (dp[mask] == -1) continue;
      for (int i = 0; i < n; i++) {
        if (!is_bit(mask, i)) {
          int new_res = cnt_pos[i][MAX_M - total_sum[mask]];
          if (total_sum[mask] + min[i] <= 0)
            res = std::max(res, dp[mask] + new_res);
          if (total_sum[mask] + min[i] >= 0)
            dp[mask ^ (1 << i)] =
                std::max(dp[mask ^ (1 << i)], dp[mask] + new_res);
        }
      }
    }
    std::cout << res << "\n";
  }
  