Least Cost Bracket Sequence | JXNUOJhttps://acs.jxnu.edu.cn/problem/CF3D这是另一个有关括号规则的规律问题。

如果插入“+“和”1我们得到一个规律的数学表达式，例如序列(())()", "()“和”(()(()))“是规律的，而”)(", "(()“和”(()))(“不是。你有一个由字符组成的括号序列的模式”(", ")“和”?“.你必须用一个字符替换每个字符”?“以便你可以得到一个规则的括号序列。

对于每个字符“?“将其替换为(“和”)“的消耗给出了，在所有可能的变式中，你应该选择最少消耗的。

输入：

第一行包括一个长度为偶数的非空字符串，由字符“(", ")“和”?“组成。它的长度不超过5*1e4,。然后跟着m行，m是字符“？”的数量。在每一行包含两个整数ai和bi (1≤ai,  bi≤106)，ai表示用括号替换第i个字符“?“的消耗，bi是另一个。

输出：
在第一行中打印最佳规律括号序列的消耗，在第二行中打印出所需顺序。

如果没有答案的话打印出-1。如果答案不唯一，请打印其中任何一个。