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.io.*;
  import java.util.*;
  
  public class Main2{
  	static int n;
  	static char[][]in;
  	static TreeSet[][]occ;
  	static int[]minPrefBal,balance;
  	static int[][]minIdx;
  	static int[]memo;
  	static int dp(int msk,int bal){
  		if(memo[msk]!=-1)return memo[msk];
  		int ans=0;
  		for(int i=0;i<n;i++){
  			if(((msk>>i)&1)==1)continue;
  			if(bal+minPrefBal[i]>=0){
  				int cnt=bal>=occ[i].length?0:occ[i][bal].size();
  				ans= Math.max(ans,cnt+dp(msk|(1<<i),bal+balance[i]));
  				continue;
  			}
  			//taking i would make all future prefixe non regular
  			int firstIdx=minIdx[i][bal+1];//first idx that make sequence non regular
  			int[]lastValidPref= (int[]) occ[i][bal].lower(new int[]{firstIdx});
  			if(lastValidPref!=null){
  				ans=Math.max(ans,lastValidPref[1]);
  			}
  		}
  		return memo[msk]=ans;
  	}
  	static void main() throws Exception{
  		n=sc.nextInt();
  		in=new char[n][];
  		occ=new TreeSet[n][];
  		minPrefBal=new int[n];
  		minIdx=new int[n][];
  		balance=new int[n];
  		for(int i=0;i<n;i++){
  			in[i]=sc.nextLine().toCharArray();
  			occ[i]=new TreeSet[in[i].length+1];
  			minIdx[i]=new int[in[i].length+1];
  			for(int j=0;j<=in[i].length;j++){
  				minIdx[i][j]=in[i].length+7;
  				occ[i][j]=new TreeSet<int[]>((x,y)->x[0]-y[0]);
  			}
  			int bal=0;
  			for(int j=0;j<in[i].length;j++){
  				bal+=(in[i][j]=='('?1:-1);
  				minPrefBal[i]= Math.min(minPrefBal[i], bal);
  				if(bal<=0){
  					occ[i][-bal].add(new int[]{j,occ[i][-bal].size()+1});
  					minIdx[i][-bal]=Math.min(minIdx[i][-bal],j);
  				}
  
  			}
  			balance[i]=bal;
  			for(int j=minIdx[i].length-2;j>=0;j--){
  				minIdx[i][j]=Math.min(minIdx[i][j],minIdx[i][j+1]);
  			}
  		}
  //		System.out.println(Arrays.toString(balance)+" "+Arrays.toString(minPrefBal)+" "+Arrays.deepToString(minIdx));
  		memo=new int[1<<n];
  		Arrays.fill(memo,-1);
  		pw.println(dp(0,0));
  	}
  	public static void main(String[] args) throws Exception{
  		sc=new MScanner(System.in);
  //		sc=new MScanner(" .in");
  		pw = new PrintWriter(System.out);
  		int tc=1;
  //		tc=sc.nextInt();
  		for(curt=1;curt<=tc;curt++) {
  //			pw.printf("Case #%d: ", curt);
  			main();
  		}
  
  		pw.flush();
  	}
  	static int curt;
  	static PrintWriter pw;
  	static MScanner sc;
  	static class MScanner {
  		StringTokenizer st;
  		BufferedReader br;
  		public MScanner(InputStream system) {
  			br = new BufferedReader(new InputStreamReader(system));
  		}
  
  		public MScanner(String file) throws Exception {
  			br = new BufferedReader(new FileReader(file));
  		}
  
  		public String next() throws IOException {
  			while (st == null || !st.hasMoreTokens())
  				st = new StringTokenizer(br.readLine());
  			return st.nextToken();
  		}
  		public int[] intArr(int n) throws IOException {
  			int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
  			return in;
  		}
  		public long[] longArr(int n) throws IOException {
  			long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
  			return in;
  		}
  		public int[] intSortedArr(int n) throws IOException {
  			int[]in=new int[n];for(int i=0;i<n;i++)in[i]=nextInt();
  			shuffle(in);
  			Arrays.sort(in);
  			return in;
  		}
  		public long[] longSortedArr(int n) throws IOException {
  			long[]in=new long[n];for(int i=0;i<n;i++)in[i]=nextLong();
  			shuffle(in);
  			Arrays.sort(in);
  			return in;
  		}
  		public Integer[] IntegerArr(int n) throws IOException {
  			Integer[]in=new Integer[n];for(int i=0;i<n;i++)in[i]=nextInt();
  			return in;
  		}
  		public Long[] LongArr(int n) throws IOException {
  			Long[]in=new Long[n];for(int i=0;i<n;i++)in[i]=nextLong();
  			return in;
  		}
  		public String nextLine() throws IOException {
  			return br.readLine();
  		}
  
  		public int nextInt() throws IOException {
  			return Integer.parseInt(next());
  		}
  
  		public double nextDouble() throws IOException {
  			return Double.parseDouble(next());
  		}
  
  		public char nextChar() throws IOException {
  			return next().charAt(0);
  		}
  
  		public long nextLong() throws IOException {
  			return Long.parseLong(next());
  		}
  
  		public boolean ready() throws IOException {
  			return br.ready();
  		}
  
  		public void waitForInput() throws InterruptedException {
  			Thread.sleep(3000);
  		}
  
  	}
  	static void dbg(int[]in) {
  		System.out.println(Arrays.toString(in));
  	}
  	static void dbg(long[]in) {
  		System.out.println(Arrays.toString(in));
  	}
  	static void sort(int[]in) {
  		shuffle(in);
  		Arrays.sort(in);
  	}
  	static void sort(long[]in) {
  		shuffle(in);
  		Arrays.sort(in);
  	}
  	static void shuffle(int[]in) {
  		for(int i=0;i<in.length;i++) {
  			int idx=(int)(Math.random()*in.length);
  			int tmp=in[i];
  			in[i]=in[idx];
  			in[idx]=tmp;
  		}
  	}
  	static void shuffle(long[]in) {
  		for(int i=0;i<in.length;i++) {
  			int idx=(int)(Math.random()*in.length);
  			long tmp=in[i];
  			in[i]=in[idx];
  			in[idx]=tmp;
  		}
  	}
  }