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 Main {
  	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
  	static StringTokenizer st;
  	static PrintWriter pr = new PrintWriter(System.out);
  	static String readLine() throws IOException {
  		return br.readLine();
  	}
  	static String next() throws IOException {
  		while (st == null || !st.hasMoreTokens())
  			st = new StringTokenizer(readLine());
  		return st.nextToken();
  	}
  	static int readInt() throws IOException {
  		return Integer.parseInt(next());
  	}
  	static long readLong() throws IOException {
  		return Long.parseLong(next());
  	}
  	static double readDouble() throws IOException {
  		return Double.parseDouble(next());
  	}
  	static char readChar() throws IOException {
  		return next().charAt(0);
  	}
  	static class Pair implements Comparable<Pair> {
  		int f, s;
  		Pair(int f, int s) {
  			this.f = f; this.s = s;
  		}
  		public int compareTo(Pair other) {
  			if (this.f != other.f) return this.f - other.f;
  			return this.s - other.s;
  		}
  	}
  	final static int M = (int)1e6, shift = (int)5e5;
  	static void solve() throws IOException {
  		int n = readInt(), net[] = new int[n], min[] = new int[n];
  		int fre1[][] = new int[n][M], fre2[][] = new int[n][M];
  		for (int i = 0; i < n; ++i) {
  			String s = readLine();
  			for (int j = 0; j < s.length(); ++j) {
  				if (s.charAt(j) == '(') ++net[i];
  				else --net[i];
  				min[i] = Math.min(min[i], net[i]);
  				if (min[i] >= net[i]) ++fre1[i][net[i] + shift];
  				++fre2[i][net[i] + shift];
  			}
  		}
  		int full = (1<<n) - 1, dp[] = new int[1<<n];
  		//full is the full mask
  		//dp[mask] = max number of regular bracket sequences given that the overall sequence is still regular
  		Arrays.fill(dp, -M);
  		dp[0] = 0;
  		int ans = 0;
  		for (int mask = 0; mask < full; ++mask) {
  			int sum = 0;
  			for (int i = 0; i < n; ++i)
  				if ((mask>>i&1) == 1) sum += net[i];
  			for (int i = 0; i < n; ++i) {
  				if ((mask>>i&1) == 1) continue;
  				if (sum + min[i] >= 0) {
  					int new_mask = mask|1<<i;
  					dp[new_mask] = Math.max(dp[new_mask], dp[mask] + fre2[i][-sum + shift]);
  				} else ans = Math.max(ans, dp[mask] + fre1[i][-sum + shift]);
  			}
  		}
  		ans = Math.max(ans, dp[full]);
  		pr.println(ans);
  	}
  	public static void main(String[] args) throws IOException {
  		solve();
  		//for (int t = readInt(); t > 0; --t) solve();
  		pr.close();
  	}
  }
  