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.
1
)(((((()((())(((((((
 1
)()())((()))((()((()
 10
((((((((((((((((()))))))))))))))))
(((((((((((((((())))))))))))))))
((((((((((((((((((((()))))))))))))))))))))
(((((((((((((((((((((())))))))))))))))))))))
()()()()()()()()()()()()()()()()()()()()
()()()()()()()()()()()()()()()()()()()()()()()()()()
(((((((((((((((((())))))))))))))))))
()()()()()()()()()()()()()()()()()()()
()()()()()()()()()()()()()()()()()()
()()()()()()()()()()()()()()()()()()()()()()()
 20
)
(
)
)
)
)
)
(
(
)
)
)
)
(
)
)
)
)
(
)
 6
()()()()()
()()()()
()
((((()))))
((()))
()()
 1
((((((((((((((((((((
 10
((((((((((((((((((((((((()))))))))))))))))))))))))
()()()()()()()()()()()()()()()()()()()
(((((((((((((((((())))))))))))))))))
()()()()()()()()()()()()()()()()()()()()()()
((((((((((((((((((()))))))))))))))))))
((((((((((((((((((((((()))))))))))))))))))))))
()()()()()()()()()()()()()()()()()()()
((((((((((((((()))))))))))))))
()()()()()()()()()()()()()()()()()()()()()()()()
()()()()()()()()()()()()()()()()
 2
))())))((()
()((((((()))))))(()
 20
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
)
 20
(
(
)
(
(
)
(
(
(
(
(
(
)
)
(
(
(
(
(
)
 10
()()
(())
()()
()()
(())
(((())))
()
(())
()()
()
 1
))))))))))))))))))))
 6
(((())))
(((())))
()()()
(())
()()()()()
()()
 10
)
)
))
))
))
))
))
))
)))
)))
 10
)()
()
)
)
)
)(
)))
)(
(((
))
 20
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
(
 10
))
()(
(
()
()
((((
(
(
(((
(
 10
()
()()()()
(())
((()))
(())
()()
(())
()()
()
()
 10
())
()
)
)))
))
()
)
))
)))
)
 1
))))))()))())(()))))
 10
((
(((
(
(((
((((
((
(
(
(
((
 20
)
(
(
)
)
(
)
(
(
(
)
)
)
)
(
)
(
(
)
(

0
 0
 111
 5
 14
 0
 105
 3
 0
 5
 14
 0
 13
 0
 5
 0
 4
 15
 3
 0
 0
 10

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;
		}
	}
}