괄호 채우기

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

요약

모든 ?를 ( 또는 )로 바꾸어 비용이 가장 작은 올바른 괄호 문자열을 만들고 동점인 경우 사전 순으로 가장 앞선 것을 출력합니다.

난이도: 보통10점 중 7점
유형: 그리디, 힙
정답자: 아직 제출이 없습니다

문제

(와 ) 두 기호만으로 만들 수 있는 문자열을 괄호열이라고 한다. 괄호열에 +와 1을 알맞게 끼워 넣어 올바른 수식을 만들 수 있으면, 그 괄호열을 올바른 괄호열이라고 한다. 예를 들어 (()(()))와 ()(()(())())는 올바른 괄호열이고, )(와 (()))()는 올바른 괄호열이 아니다.

채점 데이터마다 올바른 괄호열이 하나씩 들어 있었는데, 파일을 열어 보니 괄호열의 일부가 ?로 바뀌어 있었다. 손상된 데이터는 (())(?()())?()?(?처럼 보인다. 각 ?는 원래 ( 또는 ) 기호 하나가 깨진 자리다.

데이터를 그대로 복구하면 문제가 너무 쉬워지므로, 왼쪽에서 $i$ 번째 ?를 (로 바꾸는 비용 $l_i$ 와 )로 바꾸는 비용 $r_i$ 를 미리 정해 두었다. 복구 비용은 각 ?를 바꾸는 데 드는 비용의 합이다.

모든 ?를 ( 또는 )로 바꾸어 올바른 괄호열을 만들되, 총 비용을 가장 적게 하는 프로그램을 작성하시오. 최소 비용을 내는 괄호열이 여러 개면 그중 사전순으로 가장 앞서는 것을 구한다. 사전순 비교에서 (는 )보다 앞선다.

입력

첫째 줄에 손상된 괄호열의 길이 $N$ 이 주어진다. $N$ 은 짝수이고 $2 \le N \le 100000$ 이다.

둘째 줄에 (, ), ?로만 이루어진 손상된 괄호열이 주어진다.

?의 개수를 $Q$ 라고 하면 $1 \le Q \le N$ 이고, 이어지는 $Q$ 개 줄에 왼쪽에서 $i$ 번째 ?의 비용 $l_i$ 와 $r_i$ 가 공백을 사이에 두고 주어진다 ( $1 \le l_i, r_i \le 100000$ ).

모든 ?를 알맞게 바꾸어 올바른 괄호열을 만드는 방법이 적어도 하나 있음이 보장된다.

출력

첫째 줄에 최소 비용을 출력한다.

둘째 줄에 그 비용으로 만들 수 있는 괄호열 중 사전순으로 가장 앞서는 것을 출력한다.

예제6

예제 1
입력
```
4
(??)
3 5
7 4
```
예상 출력
```
7
(())
```
예제 2
입력
```
6
((())?
5 6
```
예상 출력
```
6
((()))
```
예제 3
입력
```
2
??
1 1
1 1
```
예상 출력
```
2
()
```
예제 4
입력
```
2
?)
4 9
```
예상 출력
```
4
()
```
예제 5
입력
```
4
????
1 3
3 1
3 1
1 3
```
예상 출력
```
8
(())
```
예제 6
입력
```
6
(((??)
100 1
100 2
```
예상 출력
```
3
((()))
```