Balanced Sequence

시간 제한1초메모리 제한256 MB

요약

여러 개의 괄호 문자열을 재배열해 이어 붙일 때, 가장 긴 균형 부분 수열의 길이를 최대로 만드는 값을 구한다.

난이도: 어려움10점 중 8점
유형: 그리디, 정렬, 문자열, 스택
정답자: 아직 제출이 없습니다

문제

Chiaki는 '('와 ')'로 이루어진 $n$ 개의 문자열 $s_1, s_2, \dots, s_n$ 을 가지고 있다. 이런 문자열이 balanced하다는 것은 다음과 같다.

빈 문자열이다.
$A$ 와 $B$ 가 balanced하면 $AB$ 도 balanced하다.
$A$ 가 balanced하면 $(A)$ 도 balanced하다.

Chiaki는 문자열들의 순서를 바꾼 뒤 이어 붙여 새로운 문자열 $t$ 를 만들 수 있다. $f(t)$ 를 $t$ 의 가장 긴 balanced 부분수열(연속하지 않아도 된다)의 길이라고 하자. Chiaki는 가능한 모든 $t$ 에 대한 $f(t)$ 의 최댓값을 알고 싶어 한다.

입력

여러 개의 테스트 케이스가 주어진다. 입력의 첫째 줄에는 테스트 케이스의 수를 나타내는 정수 $T$ 가 주어진다. 각 테스트 케이스는 다음과 같다.

첫째 줄에는 정수 $n$ ( $1 \le n \le 10^5$ )이 주어진다. 이는 문자열의 개수이다.

다음 $n$ 개의 줄에는 각각 '('와 ')'로 이루어진 문자열 $s_i$ ( $1 \le |s_i| \le 10^5$ )가 주어진다.

모든 $|s_i|$ 의 합은 $5 \times 10^6$ 을 넘지 않는다.

출력

각 테스트 케이스마다 답을 나타내는 정수를 한 줄에 출력한다.

예제1

예제 1
입력
```
2
1
)()(()(
2
)
)(
```
예상 출력
```
4
2
```