Least Cost Bracket Sequence
题目（https://acs.jxnu.edu.cn/problem/CF3D）描述：
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.
输入：
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 ai and bi (1?≤?ai,??bi?≤?106), where ai is the cost of replacing the i-th character "?" with an opening bracket, and bi — with a closing one.
输出：
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 2
2 8
样例输出：
4
()()
翻译：
这是另一种的关于规则括号序列的问题。
如果一个括号序列通过插入“+”和“1”后可以得到一个正确的数学表达式，那么我们称这个括号序列是规则的。例如序列 "(())()", "()" and "(()(()))" 都是规则的,而序列")(", "(()" and "(()))("都不是规则的。你有一种括号序列的模式是这样的，它包含“（”“）”和“？”。你必须用括号替换“？”以至于你可以得到一个规则的括号序列。
对于每个“？”你可以用“（”或“）”替换它。你必须选出一种最廉价的方法实现。
输入：
第一行包含一个没有空格的序列，序列包含“（”，“）”和“？”，序列的长度不会超过50000.接下来m（m为“？”的个数）行，每行包含两个整数ai 和 bi (1?≤?ai,??bi?≤?1000000)ai表示用“（”替换第i个“？”的花费，bi表示用“）”替换第i个“？”的花费。
输出：
第一行打印实现替换的所需的最小花费，第二行打印替换后的序列，如果没有答案，打印-1。如果答案不止一种，打印任意一种。、
样例输入：
(??)
1 2
2 8
样例输出：
4
()()