RBS solution codeforces

RBS solution codeforces

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 𝑠1,𝑠2,…,𝑠𝑛s1,s2,…,sn. 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 𝑠1+𝑠2+β‹―+𝑠𝑛s1+s2+β‹―+sn has as many non-empty prefixes that are RBS as possible.

Input

The first line contains a single integer 𝑛n (1≀𝑛≀201≀n≀20).

Then 𝑛n lines follow, the 𝑖i-th of them contains 𝑠𝑖siΒ β€” a bracket sequence (a string consisting of characters “(” and/or “)“. All sequences 𝑠𝑖siare non-empty, their total length does not exceed 4β‹…1054β‹…105.

Output

Print one integerΒ β€” the maximum number of non-empty prefixes that are RBS for the string 𝑠1+𝑠2+β‹―+𝑠𝑛s1+s2+β‹―+sn, if the strings 𝑠1,𝑠2,…,𝑠𝑛s1,s2,…,sn can be rearranged arbitrarily.

Examples
input

Copy
2
(
)
output

Copy
1
input

Copy
4
()()())
(
(
)
output

Copy
4
input

Copy
1
(())
output

Copy
1
input

Copy
1
)(()
output

Copy
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.

 

Leave a Comment