这是常规括号序列的另一个问题。
如果通过在其中插入“+”和“1”得到正确的数学表达式,则括号序列称为正则括号序列。例如,序列“(())()”、“()”和“(()(()))”是常规序列,而“)(”、“(()”和“(()))(”则不是。您有一个由字符“(”、“)”和“?”组成的括号序列模式。您必须将每个字符“?”替换为括号,这样才能得到常规括号序列。
对于每个字符“?”给出了用“(”和“)”替换它的成本。在所有可能的变体中,您应该选择最便宜的。
输入
第一行包含偶数长度的非空模式,由字符“(”、“)”和“?”组成。其长度不超过5·104。接下来是m行,其中m是字符“?”的数量。在模式中。每行包含两个整数ai和bi(1≤ai,bi≤106),其中ai是替换第i个字符“?”的成本带左括号,bi - 带右括号。
输出
在第一行中打印最佳正则括号序列的成本,在第二行中打印所需的序列。
如果没有答案,则打印 -1。如果答案不唯一,请打印其中任何一个。
示例
输入 #1
(??) 1 2 2 8
输出 #1
4 ()()