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

 bool TEST = false;

using namespace std;
#include<bits/stdc++.h>
#include<fstream>

#define rep(i,n) for(int (i)=0;(i)<(ll)(n);i++)
#define rrep(i,n) for(int (i)=(ll)(n)-1;(i)>=0;i--)
#define range(i,start,end,step) for(int (i)=start;(i)<(ll)(end);(i)+=(step))
#define rrange(i,start,end,step) for(int (i)=start;(i)>(ll)(end);(i)+=(step))

#define dump(x)  cerr << "Line " << __LINE__ << ": " <<  #x << " = " << (x) << "\n";
#define spa << " " <<
#define fi first
#define se second
#define all(a)  (a).begin(),(a).end()
#define allr(a)  (a).rbegin(),(a).rend()

using ld = long double;
using ll = long long;
using ull = unsigned long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using pdd = pair<ld, ld>;
 
template<typename T> using V = vector<T>;
template<typename T> using VV = V<V<T>>;
template<typename T, typename T2> using P = pair<T, T2>;
template<typename T, typename T2> using M = map<T, T2>;
template<typename T> using S = set<T>;
template<typename T, typename T2> using UM = unordered_map<T, T2>;
template<typename T> using PQ = priority_queue<T, V<T>, greater<T>>;
template<typename T> using rPQ = priority_queue<T, V<T>, less<T>>;
template<typename T> vector<T> make_vec(size_t n, T a) { return vector<T>(n, a); }
template<typename... Ts> auto make_vec(size_t n, Ts... ts) { return vector<decltype(make_vec(ts...))>(n, make_vec(ts...)); }
template<class SS, class T> ostream& operator << (ostream& os, const pair<SS, T> v){os << "(" << v.first << ", " << v.second << ")"; return os;}
template<typename T> ostream& operator<<(ostream &os, const vector<T> &v) { for (auto &e : v) os << e << ' '; return os; }
template<class T> ostream& operator<<(ostream& os, const vector<vector<T>> &v){ for(auto &e : v){os << e << "\n";} return os;}
struct fast_ios { fast_ios(){ cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(20); }; } fast_ios_;
 
template <class T> void UNIQUE(vector<T> &x) {sort(all(x));x.erase(unique(all(x)), x.end());}
template<class T> bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b) { if (a>b) { a=b; return 1; } return 0; }
void fail() { cout << -1 << '\n'; exit(0); }
inline int popcount(const int x) { return __builtin_popcount(x); }
inline int popcount(const ll x) { return __builtin_popcountll(x); }
template<typename T> void debug(vector<vector<T>>&v){for(ll i=0;i<v.size();i++)
{cerr<<v[i][0];for(ll j=1;j<v[i].size();j++)cerr spa v[i][j];cerr<<"\n";}};
template<typename T> void debug(vector<T>&v){if(v.size()!=0)cerr<<v[0];
for(ll i=1;i<v.size();i++)cerr spa v[i];
cerr<<"\n";};
template<typename T> P<T,T> divmod(T a, T b) {return make_pair(a/b, a%b);}

const ll INF = (1ll<<62);
// const ld EPS   = 1e-10;
// const ld PI    = acos(-1.0);

template<typename T>
struct Counter {
    int n;
    int B = 300;
    V<unordered_map<T,int>> values;
    V<T> a;
    Counter(int n, V<T> b): n(n) {
        values = V<unordered_map<T,int>>((n+B-1)/B);
        rep(i,b.size()) {
            auto v = b[i];
            values[i/B][v]++;
        }
        a = b;
    }
    int query(int l, int r, T v) {
        return query(r, v) - query(l, v);
    }
    int query(int l, T v) {
        int res = 0;
        rep(i, l/B) res += values[i][v];
        range(j, (l/B)*B, l, 1) if (a[j]==v) res++;
        return res;
    }
};

void Main(){
    ll n;
    cin >> n;
    V<int> total;
    V<int> bottom;
    V<int> ls;
    V<unordered_map<int,int>> index_list;
    V<unordered_map<int,int>> counts;
    V<unordered_map<int,int>> counts2;
    rep(i,n) {
        string s;
        cin >> s;
        unordered_map<int,int> vs;
        unordered_map<int,int> index;
        unordered_map<int,int> count;
        int v = 0;
        int mm = 0;
        rep(j, s.size()) {
            if (s[j]=='(') v++;
            else v--;
            vs[v]++;
            if (index.find(v)==index.end()) {index[v] = j; count[v] = vs[v+1];}
            chmin(mm, v);
        }
        index_list.push_back(index);
        counts.push_back(count);
        counts2.push_back(vs);
        ls.push_back(vs.size());
        total.push_back(v);
        bottom.push_back(mm);
    }
    V<int> dp(1<<n);
    V<int> dp1(1<<n);
    V<int> dp2(1<<n);
    dp2[0] = 1;
    int ans = 0;
    rep(b, 1<<n) {
        if (dp2[b]==0) continue;
        int s = dp[b];
        int v = dp1[b];
        rep(i,n) {
            if (b>>i&1) continue;
            int tt = total[i];
            int mm = bottom[i];
            bool valid = 1;
            int ns, nv, nb;
            nb = b | (1<<i);
            if (mm + s < 0) {
                valid = 0;
                // int ind = index_list[i][-s-1];
                ns = s + tt;
                nv = v + counts[i][-s-1];
                // if (i==0) cout << ind spa -s spa counts[i].query(ind, -s) << endl;
            } else {
                ns = s + tt;
                nv = v + counts2[i][-s];
            }
            dp2[nb] = valid;
            dp[nb] = ns;
            dp1[nb] = max(dp1[nb], nv);
            chmax(ans, nv);
            // if (nv==2) cout << b spa i << endl;
        }
    }
    // debug(dp);
    // debug(dp1);
    cout << ans << endl;
}

int main(void){
    std::ifstream in("tmp_in");
    if (TEST) {
        std::cin.rdbuf(in.rdbuf());
        std::cout << std::fixed << std::setprecision(15);
    } else {
        std::cin.tie(nullptr);
        std::ios_base::sync_with_stdio(false);
        std::cout << std::fixed << std::setprecision(15);
    }
    Main();
}
