One day, Yuhao came across a problem about checking if some bracket sequences are correct bracket sequences.

A bracket sequence is any non-empty sequence of opening and closing parentheses. A bracket sequence is called a correct bracket sequence if it's possible to obtain a correct arithmetic expression by inserting characters "+" and "1" into this sequence. For example, the sequences "(())()", "()" and "(()(()))" are correct, while the bracket sequences ")(", "(()" and "(()))(" are not correct.

Yuhao found this problem too simple for him so he decided to make the problem harder. You are given many (not necessarily correct) bracket sequences. The task is to connect some of them into ordered pairs so that each bracket sequence occurs in at most one pair and the concatenation of the bracket sequences in each pair is a correct bracket sequence. The goal is to create as many pairs as possible.

This problem unfortunately turned out to be too difficult for Yuhao. Can you help him and solve it?

Input

The first line contains one integer n (1 ≤ n ≤ 10^5) — the number of bracket sequences.

Each of the following n lines contains one bracket sequence — a non-empty string which consists only of characters "(" and ")".

The sum of lengths of all bracket sequences in the input is at most 5 ⋅ 10^5.

Note that a bracket sequence may appear in the input multiple times. In this case, you can use each copy of the sequence separately. Also note that the order in which strings appear in the input doesn't matter.

Output

Print a single integer — the maximum number of pairs which can be made, adhering to the conditions in the statement.

Examples

Input


7
)())
)
((
((
(
)
)


Output


2


Input


4
(
((
(((
(())


Output


0


Input


2
(())
()


Output


1

Note

In the first example, it's optimal to construct two pairs: "(( )())" and "( )".
// package Hello2019;

import java.io.*;
import java.util.*;

/*
    Author - Ribhav
    MADE ON - 1/4/2019
*/

public class HC {
    static FastReader s;
    static PrintWriter out;
    static String INPUT = "2\n" +
            "(())\n" +
            "()\n";

    public static void main(String[] args) {
        long time = System.currentTimeMillis();
        boolean oj = System.getProperty("ONLINE_JUDGE") != null;
        out = new PrintWriter(System.out);
        s = new FastReader(oj);

        int n = s.nextInt();
        ArrayList<String> set = new ArrayList<>();
//        int[] arr = s.nextIntArray(n);
        String[] arr = new String[n];
        for (int i = 0; i < n; i++) {
            arr[i] = s.next();
        }
//        Arrays.sort(arr);


        HashMap<Integer, Integer> mapOpensR = new HashMap<>();
        HashSet<Integer> zero = new HashSet<>();
        HashMap<Integer, Integer> mapOpensL = new HashMap<>();
        for (int i = 0; i < n; i++) {
            Stack<Character> stack = new Stack<>();
            for (int j = 0; j < arr[i].length(); j++) {
                if (arr[i].charAt(j) == '(') {
                    stack.push('(');
                } else {
                    if (!stack.isEmpty() && stack.peek() == '(') {
                        stack.pop();
                    } else if (!stack.isEmpty() && stack.peek() == ')') {
                        stack.push(')');
                    } else {
                        stack.push(')');
                    }
                }
            }

            if (stack.isEmpty()) {
//                ArrayList<Integer> list = zero.getOrDefault(0, new ArrayList<>());
//                list.add(i);
                zero.add(i);
            } else {
                char ch = stack.peek();
                boolean bool = false;
                int count = 0;
                while (!stack.isEmpty()) {
                    if (stack.pop() != ch) {
                        bool = true;
                        break;
                    } else {
                        count++;
                    }
                }

                if (!bool) {
                    if (ch == '(') {
                        mapOpensR.put(count, mapOpensR.getOrDefault(count, 0) + 1);
                    } else {
                        mapOpensL.put(count, mapOpensL.getOrDefault(count, 0) + 1);
                    }
                }
            }

        }

        ArrayList<Integer> listR = new ArrayList<>(mapOpensR.keySet());
        long ans = 0;
        for (int i = 0; i < listR.size(); i++) {
            int k = listR.get(i);
            int list2 = mapOpensL.getOrDefault(k, 0);
            int list1 = mapOpensR.getOrDefault(k, 0);
            ans += Math.min(list1, list2);
        }

        int list2 = zero.size();
        ans += list2 / 2;


        out.println(ans);


        if (!oj) {
            System.out.println(Arrays.deepToString(new Object[]{System.currentTimeMillis() - time + " ms"}));
        }
        out.flush();
    }


    static ArrayList<Long> printDivisors(long n) {
        // Note that this loop runs till square root
        ArrayList<Long> list = new ArrayList<>();
        for (long i = 1; i <= Math.sqrt(n); i++) {
            if (n % i == 0) {
                if (n / i == i) {
                    list.add(i);
                } else {
                    list.add(i);
                    list.add(n / i);
                }
            }
        }
        return list;
    }


    //    GCD - Using Euclid theorem.
    private static long gcd(long a, long b) {
        if (b == 0) {
            return a;
        }

        return gcd(b, a % b);
    }

    //    Extended euclidean algorithm
//    Used to solve equations of the form ax + by = gcd(a,b)
//    return array [d, a, b] such that d = gcd(p, q), ap + bq = d
    static long[] extendedEuclidean(long p, long q) {
        if (q == 0)
            return new long[]{p, 1, 0};

        long[] vals = extendedEuclidean(q, p % q);
        long d = vals[0];
        long a = vals[2];
        long b = vals[1] - (p / q) * vals[2];
        return new long[]{d, a, b};
    }

    // X ^ y mod p
    static long power(long x, long y, long p) {
        long res = 1;
        x = x % p;

        while (y > 0) {
            if ((y & 1) == 1)
                res = (res * x) % p;
            y = y >> 1;
            x = (x * x) % p;
        }
        return res;
    }

    // Returns modulo inverse of a
    // with respect to m using extended
    // Euclid Algorithm. Refer below post for details:
    // https://www.geeksforgeeks.org/multiplicative-inverse-under-modulo-m/
    static long inv(long a, long m) {
        long m0 = m, t, q;
        long x0 = 0, x1 = 1;

        if (m == 1)
            return 0;

        // Apply extended Euclid Algorithm
        while (a > 1) {
            q = a / m;
            t = m;
            m = a % m;
            a = t;
            t = x0;
            x0 = x1 - q * x0;
            x1 = t;
        }

        // Make x1 positive
        if (x1 < 0)
            x1 += m0;

        return x1;
    }

    // k is size of num[] and rem[].
    // Returns the smallest number
    // x such that:
    // x % num[0] = rem[0],
    // x % num[1] = rem[1],
    // ..................
    // x % num[k-2] = rem[k-1]
    // Assumption: Numbers in num[] are pairwise
    // coprime (gcd for every pair is 1)
    static long findMinX(long num[], long rem[], long k) {
        int prod = 1;
        for (int i = 0; i < k; i++)
            prod *= num[i];

        int result = 0;
        for (int i = 0; i < k; i++) {
            long pp = prod / num[i];
            result += rem[i] * inv(pp, num[i]) * pp;
        }

        return result % prod;
    }

    //  Binary search
    private static int binarySearch(int[] arr, int ele) {
        int low = 0;
        int high = arr.length - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == ele) {
                return mid;
            } else if (ele < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    //    First occurence using binary search
    private static int binarySearchFirstOccurence(int[] arr, int ele) {
        int low = 0;
        int high = arr.length - 1;
        int ans = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == ele) {
                ans = mid;
                high = mid - 1;
            } else if (ele < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }


    //    Last occurenece using binary search
    private static int binarySearchLastOccurence(int[] arr, int ele) {
        int low = 0;
        int high = arr.length - 1;
        int ans = -1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (arr[mid] == ele) {
                ans = mid;
                low = mid + 1;
            } else if (ele < arr[mid]) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return ans;
    }


    // Merge sort
    static void merge(int arr[], int l, int m, int r) {
        int n1 = m - l + 1;
        int n2 = r - m;
        int L[] = new int[n1];
        int R[] = new int[n2];
        for (int i = 0; i < n1; ++i)
            L[i] = arr[l + i];
        for (int j = 0; j < n2; ++j)
            R[j] = arr[m + 1 + j];
        int i = 0, j = 0;
        int k = l;
        while (i < n1 && j < n2) {
            if (L[i] <= R[j]) {
                arr[k] = L[i];
                i++;
            } else {
                arr[k] = R[j];
                j++;
            }
            k++;
        }

        while (i < n1) {
            arr[k] = L[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = R[j];
            j++;
            k++;
        }
    }

    static void sort(int arr[], int l, int r) {
        if (l < r) {
            int m = (l + r) / 2;
            sort(arr, l, m);
            sort(arr, m + 1, r);
            merge(arr, l, m, r);
        }
    }

    static void sort(int[] arr) {
        sort(arr, 0, arr.length - 1);
    }

    static class FastReader {
        InputStream is;

        public FastReader(boolean oj) {
            is = oj ? System.in : new ByteArrayInputStream(INPUT.getBytes());
        }

        byte[] inbuf = new byte[1024];
        public int lenbuf = 0, ptrbuf = 0;

        public int readByte() {
            if (lenbuf == -1)
                throw new InputMismatchException();
            if (ptrbuf >= lenbuf) {
                ptrbuf = 0;
                try {
                    lenbuf = is.read(inbuf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (lenbuf <= 0)
                    return -1;
            }
            return inbuf[ptrbuf++];
        }

        public boolean isSpaceChar(int c) {
            return !(c >= 33 && c <= 126);
        }

        public int skip() {
            int b;
            while ((b = readByte()) != -1 && isSpaceChar(b))
                ;
            return b;
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public char nextChar() {
            return (char) skip();
        }

        public String next() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while (!(isSpaceChar(b))) { // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public String nextLine() {
            int b = skip();
            StringBuilder sb = new StringBuilder();
            while ((!isSpaceChar(b) || b == ' ')) { // when nextLine, (isSpaceChar(b) && b != ' ')
                sb.appendCodePoint(b);
                b = readByte();
            }
            return sb.toString();
        }

        public char[] next(int n) {
            char[] buf = new char[n];
            int b = skip(), p = 0;
            while (p < n && !(isSpaceChar(b))) {
                buf[p++] = (char) b;
                b = readByte();
            }
            return n == p ? buf : Arrays.copyOf(buf, p);
        }

        public int nextInt() {
            int num = 0, b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
                ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = num * 10 + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public long nextLong() {
            long num = 0;
            int b;
            boolean minus = false;
            while ((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'))
                ;
            if (b == '-') {
                minus = true;
                b = readByte();
            }

            while (true) {
                if (b >= '0' && b <= '9') {
                    num = num * 10 + (b - '0');
                } else {
                    return minus ? -num : num;
                }
                b = readByte();
            }
        }

        public char[][] nextMatrix(int n, int m) {
            char[][] map = new char[n][];
            for (int i = 0; i < n; i++)
                map[i] = next(m);
            return map;
        }

        public int[] nextIntArray(int n) {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
                a[i] = nextInt();
            return a;
        }

        public long[] nextLongArray(int n) {
            long[] a = new long[n];
            for (int i = 0; i < n; i++)
                a[i] = nextLong();
            return a;
        }

        public int[][] next2DInt(int n, int m) {
            int[][] arr = new int[n][];
            for (int i = 0; i < n; i++) {
                arr[i] = nextIntArray(m);
            }
            return arr;
        }

        public long[][] next2DLong(int n, int m) {
            long[][] arr = new long[n][];
            for (int i = 0; i < n; i++) {
                arr[i] = nextLongArray(m);
            }
            return arr;
        }

        public int[] shuffle(int[] arr) {
            Random r = new Random();
            for (int i = 1, j; i < arr.length; i++) {
                j = r.nextInt(i);
                arr[i] = arr[i] ^ arr[j];
                arr[j] = arr[i] ^ arr[j];
                arr[i] = arr[i] ^ arr[j];
            }
            return arr;
        }

        public int[] uniq(int[] arr) {
            Arrays.sort(arr);
            int[] rv = new int[arr.length];
            int pos = 0;
            rv[pos++] = arr[0];
            for (int i = 1; i < arr.length; i++) {
                if (arr[i] != arr[i - 1]) {
                    rv[pos++] = arr[i];
                }
            }
            return Arrays.copyOf(rv, pos);
        }

    }
}