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;
  using ll = long long;
  using ld = double;
  using pi = pair<int, int>;
  using pl = pair<ll, ll>;
  using pd = pair<ld, ld>;
  using cd = complex<ld>;
  using vcd = vector<cd>;
  using vi = vector<int>;
  using vl = vector<ll>;
  using vd = vector<ld>;
  using vs = vector<string>;
  using vpi = vector<pi>;
  using vpl = vector<pl>;
  using vpd = vector<pd>;
  template <class T>
  using min_pq = priority_queue<T, vector<T>, greater<T> >;
  template <class T>
  inline int ckmin(T& a, const T& val) {
    return val < a ? a = val, 1 : 0;
  }
  template <class T>
  inline int ckmax(T& a, const T& val) {
    return a < val ? a = val, 1 : 0;
  }
  template <class T>
  void remDup(vector<T>& v) {
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), end(v));
  }
  constexpr int pct(int x) { return __builtin_popcount(x); }
  constexpr int bits(int x) { return x == 0 ? 0 : 31 - __builtin_clz(x); }
  constexpr int p2(int x) { return 1 << x; }
  constexpr int msk2(int x) { return p2(x) - 1; }
  ll ceilDiv(ll a, ll b) { return a / b + ((a ^ b) > 0 && a % b); }
  ll floorDiv(ll a, ll b) { return a / b - ((a ^ b) < 0 && a % b); }
  void setPrec(int x) { cout << fixed << setprecision(x); }
  string to_string(char c) { return string(1, c); }
  string to_string(const char* s) { return (string)s; }
  string to_string(string s) { return s; }
  string to_string(bool b) { return to_string((int)b); }
  template <class T>
  string to_string(complex<T> c) {
    stringstream ss;
    ss << c;
    return ss.str();
  }
  template <class T>
  using V = vector<T>;
  string to_string(V<bool> v) {
    string res = "{";
    for (int i = (0); i <= (int((v).size()) - 1); i++) res += char('0' + v[i]);
    res += "}";
    return res;
  }
  template <size_t sz>
  string to_string(bitset<sz> b) {
    string res = "";
    for (int i = (0); i <= (int((b).size()) - 1); i++) res += char('0' + b[i]);
    return res;
  }
  template <class T, class U>
  string to_string(pair<T, U> p);
  template <class T>
  string to_string(T v) {
    bool fst = 1;
    string res = "";
    for (const auto& x : v) {
      if (!fst) res += " ";
      fst = 0;
      res += to_string(x);
    }
    return res;
  }
  template <class T, class U>
  string to_string(pair<T, U> p) {
    return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
  }
  template <class T>
  void pr(T x) {
    cout << to_string(x);
  }
  template <class T, class... U>
  void pr(const T& t, const U&... u) {
    pr(t);
    pr(u...);
  }
  void ps() { pr("\n"); }
  template <class T, class... U>
  void ps(const T& t, const U&... u) {
    pr(t);
    if (sizeof...(u)) pr(" ");
    ps(u...);
  }
  void DBG() { cerr << "]" << endl; }
  template <class T, class... U>
  void DBG(const T& t, const U&... u) {
    cerr << to_string(t);
    if (sizeof...(u)) cerr << ", ";
    DBG(u...);
  }
  const ld PI = acos(-1.0);
  const int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1};
  const ld EPS = 1e-9;
  const ll MODBASE = 1000000007LL;
  const int INF = 0x3f3f3f3f;
  const int MAXN = 20;
  const int MAXM = 1000;
  const int MAXK = 16;
  const int MAXQ = 200010;
  int n, sum[MAXN], dp[1 << MAXN][2];
  string s[MAXN];
  vector<vi> X, Y, Z;
  int main() {
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin >> n;
    for (int i = (0); i <= (n - 1); i++) cin >> s[i];
    vi x, y, z;
    for (int i = (0); i <= (n - 1); i++) {
      x.clear();
      y.clear();
      z.clear();
      for (int j = (0); j <= (int((s[i]).size()) - 1); j++) {
        if (s[i][j] == '(')
          x.push_back(1);
        else
          x.push_back(-1);
      }
      for (int j = (1); j <= (int((x).size()) - 1); j++) x[j] += x[j - 1];
      sum[i] = x.back();
      y.push_back(x[0]);
      z.push_back(1);
      for (int j = (1); j <= (int((x).size()) - 1); j++) {
        int curMin = y.back(), cntMin = z.back();
        if (x[j] < curMin) {
          curMin = x[j];
          cntMin = 1;
        } else if (x[j] == curMin)
          cntMin++;
        y.push_back(curMin);
        z.push_back(cntMin);
      }
      X.push_back(x);
      Y.push_back(y);
      Z.push_back(z);
    }
    memset(dp, -1, sizeof(dp));
    dp[0][0] = dp[0][1] = 0;
    for (int mask = (0); mask <= ((1 << n) - 1); mask++) {
      for (int p = (0); p <= (1); p++) {
        if (dp[mask][p] == -1) continue;
        if (p == 1) {
          for (int i = (0); i <= (n - 1); i++)
            if (!(mask & (1 << i))) ckmax(dp[mask | (1 << i)][1], dp[mask][1]);
          continue;
        }
        int prefixSum = 0;
        for (int i = (0); i <= (n - 1); i++)
          if (mask & (1 << i)) prefixSum += sum[i];
        for (int i = (0); i <= (n - 1); i++)
          if (!(mask & (1 << i))) {
            int newMask = mask + (1 << i);
            int newP = 0;
            int dau = 0, cuoi = int((X[i]).size()) - 1;
            while (dau <= cuoi) {
              int mid = (dau + cuoi) >> 1;
              if (Y[i][mid] < -prefixSum)
                cuoi = mid - 1;
              else
                dau = mid + 1;
            }
            int r = cuoi, dem = 0;
            if (r >= 0 && Y[i][r] == -prefixSum) dem = Z[i][r];
            if (r == int((X[i]).size()) - 1) {
              newP = 0;
            } else {
              newP = 1;
            }
            ckmax(dp[newMask][newP], dp[mask][p] + dem);
          }
      }
    }
    cout << max(dp[(1 << n) - 1][0], dp[(1 << n) - 1][1]) << "\n";
    return 0;
  }
  