#594 괄호 뒤집기

Statement

問題文の言語

길이가 $2N$ 인 괄호 문자열 $S$ 가 주어진다. $i$ 번째 괄호 문자를 뒤집는 비용은 $A_i$ 이다. 문자를 뒤집으면 (는 )가 되고, )는 (가 된다.

문자열 $S$ 가 올바른 괄호 문자열이라는 것은 다음 규칙으로 정의된다.

위 규칙을 유한 번 적용하여 만들 수 있는 문자열만을 올바른 괄호 문자열이라 한다. $S$ 의 일부 문자를 뒤집어 올바른 괄호 문자열로 만들고자 한다. 필요한 비용의 최솟값과 그 최소 비용을 사용하는 결과 문자열 하나를 출력하여라.

입력은 다음과 같은 형식으로 주어진다.

$T$ $\mathrm{case}_1$ $\mathrm{case}_2$ $\vdots$ $\mathrm{case}_T$

각 케이스는 다음과 같은 형식으로 주어진다.

$N$ $S$ $A_1\ A_2\ \cdots\ A_{2N}$

각 테스트 케이스마다 먼저 최소 비용을 한 줄에 출력한다.

다음 줄에 그 최소 비용으로 만들 수 있는 올바른 괄호 문자열을 하나 출력한다. 가능한 답이 여러 가지라면 아무거나 출력해도 된다.

入力例

2
2
()))
5 1 4 7
3
))(()(
3 8 2 6 4 5

出力例

1
(())
8
()(())

첫 번째 테스트 케이스에서는 두 번째 문자를 뒤집으면 문자열이 $\texttt{(())}$ 가 되며 비용은 $1$ 입니다. 비용 $0$ 으로는 올바른 괄호 문자열을 만들 수 없으므로 최소 비용은 $1$ 입니다.