Concatenating Parenthesis Strings

Time limit2sMemory limit128 MB

Summary

Decide whether the given parenthesis strings can be ordered so their concatenation forms a correct bracket sequence.

Level: Medium6 of 10
Topics: Greedy, Sorting, Prefix sum
Solved: No attempts yet

Problem

You are given $n$ strings $str_1, str_2, \ldots, str_n$ , each consisting of ( and ) only. Decide whether the $n$ strings can be arranged in some order so that their concatenation is a valid parenthesis string. You may reorder the strings, but the contents of each string stay as they are.

A valid parenthesis string is defined as follows.

The empty string is valid.
If $A$ and $B$ are valid, then the concatenation of $A$ and $B$ is valid.
If $A$ is valid, then the string obtained by putting $A$ inside a pair of matching parentheses is valid.
No other string is valid.

For example, ()() and (()) are valid, while ()) and ((() are not.

Input

The first line contains the number of strings $n$ ( $1 \le n \le 100$ ). Each of the next $n$ lines contains one string $str_i$ ( $1 \le |str_i| \le 100$ ). Every character of $str_i$ is ( or ).

Output

Print Yes on the first line if a valid parenthesis string can be built, and No otherwise. Do not print the quotes.

Examples5

Example 1
Input
```
3
()(()((
))()()(()
)())(())
```
Expected output
```
Yes
```
Example 2
Input
```
2
))()((
))((())(
```
Expected output
```
No
```
Example 3
Input
```
1
()
```
Expected output
```
Yes
```
Example 4
Input
```
1
)(
```
Expected output
```
No
```
Example 5
Input
```
2
((
))
```
Expected output
```
Yes
```