길이가 인 괄호 문자열 가 주어진다. 번째 괄호 문자를 뒤집는 비용은 이다. 문자를 뒤집으면 (는 )가 되고, )는 (가 된다.
문자열 가 올바른 괄호 문자열이라는 것은 다음 규칙으로 정의된다.
위 규칙을 유한 번 적용하여 만들 수 있는 문자열만을 올바른 괄호 문자열이라 한다. 의 일부 문자를 뒤집어 올바른 괄호 문자열로 만들고자 한다. 필요한 비용의 최솟값과 그 최소 비용을 사용하는 결과 문자열 하나를 출력하여라.
입력은 다음과 같은 형식으로 주어진다.
각 테스트 케이스마다 먼저 최소 비용을 한 줄에 출력한다.
다음 줄에 그 최소 비용으로 만들 수 있는 올바른 괄호 문자열을 하나 출력한다. 가능한 답이 여러 가지라면 아무거나 출력해도 된다.
첫 번째 테스트 케이스에서는 두 번째 문자를 뒤집으면 문자열이 가 되며 비용은 입니다. 비용 으로는 올바른 괄호 문자열을 만들 수 없으므로 최소 비용은 입니다.
각 케이스는 다음과 같은 형식으로 주어진다.
()| 4 | 51 | 추가적인 제약이 없다. |