Problem:


  MathJax.Hub.Config({ tex2jax: { inlineMath: [["$","$"], ["\\(","\\)"]], processEscapes: true }});

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.

Input

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

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

Sample Input 1

3
()(()((
))()()(()
)())(())

Output for the Sample Input 1

Yes

Sample Input 2

2
))()((
))((())(

Output for the Sample Input 2

No


Sample input:
3
()(()((
))()()(()
)())(())


Sample output:
Yes

Submission status: Accepted

Solution code:
def solve():
    N = int(input())
    T0 = []
    T1 = []
    su = 0
    for i in range(N):
        s = input()
        a = 0
        for c in s:
            if c == '(':
                a += 1
            elif a > 0:
                a -= 1
        b = 0
        for c in reversed(s):
            if c == ')':
                b += 1
            elif b > 0:
                b -= 1
        if b < a:
            T0.append((b, a))
        else:
            T1.append((a, b))
        su += a - b
    if su != 0:
        print("No")
        return

    def check(T, N):
        U = [0]*N
        cur = 0
        for i in range(N):
            k = -1; e = (-1000, -1000)
            for j in range(N):
                if U[j]:
                    continue
                b, a = T[j]
                if b <= cur:
                    ne = (a-b, b)
                    if e < ne:
                        k = j
                        e = ne
            if k == -1:
                return 0
            b, a = T[k]
            U[k] = 1
            cur += a-b
        return 1

    if check(T0, len(T0)) and check(T1, len(T1)):
        print("Yes")
    else:
        print("No")
solve()