Time Limit : 2 sec, Memory Limit : 131072 KB

E - Parentheses

Problem Statement

You are given $n$ strings $\mathit{str}_1, \mathit{str}_2, \ldots, \mathit{str}_n$, each consisting of ( and ). The objective is to determine whether it is possible to permute the $n$ strings so that the concatenation of the strings represents a valid string.

Validity of strings are 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$ in a pair of matching parentheses is valid.
  • Any other string is not valid.

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


The first line of the input contains an integer $n$ ($1 \leq n \leq 100$), representing the number of strings. Then $n$ lines follow, each of which contains $\mathit{str}_i$ ($1 \leq \lvert \mathit{str}_i \rvert \leq 100$). All characters in $\mathit{str}_i$ are ( or ).


Output a line with "Yes" (without quotes) if you can make a valid string, or "No" otherwise.

Sample Input 1


Output for the Sample Input 1


Sample Input 2


Output for the Sample Input 2


Source: Japan Alumni Group Spring Contest 2014 , Japan, 2014-04-13