Pieces of Parentheses

Time limit2sMemory limit512 MB

Summary

Given n pieces of parentheses, choose and order some pieces to build the longest balanced parenthesis string.

Level: Hard8 of 10
Topics: Dynamic programming, Greedy, Sorting
Solved: No attempts yet

Problem

You are teaching a class in programming, and you want to cover balanced parentheses. You have a great visual aid: a sign with a very long, balanced string of parentheses. But, alas, somehow your visual aid has been broken into pieces, and some pieces may be missing! You have to put it back together as best you can. Given the string of parentheses on each piece, what is the longest balanced string you can form by concatenating some of them in some order? Each piece may be used at most once, and the pieces cannot be reversed.

A balanced string of parentheses is defined as:

The empty string
$AB$ , where $A$ and $B$ are both balanced strings of parentheses
( $A$ ), where $A$ is a balanced string of parentheses

Input

The first line contains a single integer $n$ ( $1 \le n \le 300$ ), the number of pieces.

Each of the next $n$ lines holds a single string $s$ ( $1 \le |s| \le 300$ ) that consists only of the characters ( and ). It describes one of the pieces.

Output

Output a single integer: the length of the longest balanced string of parentheses you can form from the pieces. The empty string is technically a balanced string of parentheses, so it is always possible to form a string of length at least 0 (although the empty string is not a very effective visual aid!).

Examples2

Example 1
Input
```
3
())
((()
)()
```
Expected output
```
10
```
Example 2
Input
```
5
)))))
)
((
))((
(
```
Expected output
```
2
```