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: import java.util.*;
  import java.lang.*;
  import java.io.*;
  
  public class Main
  {
  	PrintWriter out = new PrintWriter(System.out);
  	BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer tok = new StringTokenizer("");
      String next() throws IOException {
          if (!tok.hasMoreTokens()) { tok = new StringTokenizer(in.readLine()); }
          return tok.nextToken();
      }
      int ni() throws IOException { return Integer.parseInt(next()); }
      long nl() throws IOException { return Long.parseLong(next()); }
      
      long mod=1000000007;
      
      int n;
      String[]S;
      HashMap<Integer,Integer>[]H;
      int[]E,M,D;
      
      void solve() throws IOException {
          n=ni();
          S=new String[n];
          H=new HashMap[n];
          E=new int[n];
          M=new int[n];
          
          for (int i=0;i<n;i++) {
              S[i]=next();
              H[i]=new HashMap();
              int prevmin=0;
              int minct=0;
              int ct=0;
              for (int j=0;j<S[i].length();j++)   {
                  if (S[i].charAt(j)=='(') ct++;
                  else ct--;
                  
                  if (ct==prevmin) minct++;
                  if (ct<prevmin) {
                      if (minct>0) H[i].put(prevmin,minct);
                      minct=0;
                      prevmin=ct;
                  }
              }
              if (minct>0) H[i].put(prevmin,minct);
              E[i]=ct;
              M[i]=prevmin;
          }
          
          D=new int[1<<n];
          Arrays.fill(D,-1);
          D[(1<<n)-1]=0;
          out.println(solve(0,0));
          
          out.flush();
      }
      
      int solve(int u,int curr) {
          //out.println(u+" "+curr);
          //if (u==(1<<n)-1) return 0;
          if (D[u]>-1) return D[u];
          int p=1;
          int nr=0;
          for (int i=0;i<n;i++) {
              if ((u&p)>0) { p<<=1; continue; }
              int pr=0;
              if (H[i].containsKey(curr*-1)) pr=H[i].get(curr*-1);
              if (curr!=0 && curr+M[i]<=0) pr++;
              if (curr+M[i]>=0) {
                  pr+=solve(u|p,curr+E[i]);
              }
              nr=Math.max(nr,pr);
              p<<=1;
          }
          //out.println(nr);
          return D[u]=nr;
      }
      
      int gcd(int a,int b) { return(b==0?a:gcd(b,a%b)); }
      long gcd(long a,long b) { return(b==0?a:gcd(b,a%b)); }
      long mp(long a,long p) { long r=1; while(p>0) { if ((p&1)==1) r=(r*a)%mod; p>>=1; a=(a*a)%mod; } return r; }
      
      public static void main(String[] args) throws IOException {
          new Main().solve();
      }
  }