괄호 조각

프로그래밍 수업에서 올바른 괄호 문자열을 가르치려고 한다. 아주 긴 올바른 괄호 문자열이 적힌 멋진 교구 팻말도 준비했다. 그런데 어쩌다 보니 팻말이 여러 조각으로 부서졌고, 일부 조각은 사라졌을지도 모른다! 최선을 다해 다시 맞춰 보아야 한다. 각 조각에 적힌 괄호 문자열이 주어질 때, 조각 몇 개를 골라 원하는 순서로 이어 붙여서 만들 수 있는 가장 긴 올바른 괄호 문자열은 무엇일까? 각 조각은 최대 한 번만 사용할 수 있고, 조각을 뒤집을 수는 없다.

올바른 괄호 문자열은 다음과 같이 정의한다.

1. 빈 문자열
2. $A$와 $B$가 모두 올바른 괄호 문자열일 때 $AB$
3. $A$가 올바른 괄호 문자열일 때 ($A$)

첫째 줄에 조각의 개수 $n$ ($1 \le n \le 300$)이 주어진다.

다음 $n$개의 줄에는 각각 문자열 $s$ ($1 \le |s| \le 300$)가 하나씩 주어진다. $s$는 문자 (와 )로만 이루어져 있으며, 조각 하나를 나타낸다.

조각들로 만들 수 있는 가장 긴 올바른 괄호 문자열의 길이를 정수 하나로 출력한다. 빈 문자열도 엄밀히 말하면 올바른 괄호 문자열이므로, 항상 길이가 0 이상인 문자열을 만들 수 있다 (빈 문자열은 교구로서 별 쓸모가 없겠지만).