CF3D.Least Cost Bracket Sequence

This is yet another problem on regular bracket sequences.

A bracket sequence is called regular, if by inserting "+" and "1" into it we get a correct mathematical expression. For example, sequences "(())()", "()" and "(()(()))" are regular, while ")(", "(()" and "(()))(" are not. You have a pattern of a bracket sequence that consists of characters "(", ")" and "?". You have to replace each character "?" with a bracket so, that you get a regular bracket sequence.

For each character "?" the cost of its replacement with "(" and ")" is given. Among all the possible variants your should choose the cheapest.

这又是一道关于正则括号序列的问题。

若能在括号序列中插入 “+” 和 “1” 后得到一个合法的数学表达式，则称该括号序列为正则括号序列。例如，序列 "(())()"、"()" 和 "(()(()))" 是正则括号序列，而 ")("、"(()" 和 "(()))(" 则不是。
你有一个由字符 "("、")" 和 "?" 组成的括号序列模板。你需要将每个字符 "?" 替换为一个括号（即 "(" 或 ")"），使得最终得到一个正则括号序列。

对于每个字符 "?"，分别给出了将其替换为 "(" 和 ")" 的代价。在所有可行的替换方案中，你需要选择总代价最小的一种。

The first line contains a non-empty pattern of even length, consisting of characters "(", ")" and "?". Its length doesn't exceed 5·104. Then there follow m lines, where m is the number of characters "?" in the pattern. Each line contains two integer numbers a__i and b__i (1 ≤ a__i,  b__i ≤ 106), where a__i is the cost of replacing the i-th character "?" with an opening bracket, and b__i — with a closing one.

第一行包含一个非空的、长度为偶数的模式串，由字符 "(", ")" 和 "?" 组成。该模式串的长度不超过 $5 \cdot 10^4$。随后是 $m$ 行，其中 $m$ 是模式串中字符 "?" 的个数。每行包含两个整数 $a_i$ 和 $b_i$（$1 \le a_i,\, b_i \le 10^6$），其中 $a_i$ 表示将第 $i$ 个 "?" 替换为左括号 "(" 的代价，$b_i$ 表示将其替换为右括号 ")" 的代价。

Print the cost of the optimal regular bracket sequence in the first line, and the required sequence in the second.

Print -1, if there is no answer. If the answer is not unique, print any of them.

第一行输出最优规则括号序列的代价，第二行输出对应的序列。

若不存在解，则输出 -1。若解不唯一，输出任意一个即可。