← 返回题目列表

Codeforces · 3/D

D. 最低成本括号序列

中文机器翻译题面 查看原题

这是常规括号序列的另一个问题。

如果通过在其中插入“+”和“1”得到正确的数学表达式,则括号序列称为正则括号序列。例如,序列“(())()”、“()”和“(()(()))”是常规序列,而“)(”、“(()”和“(()))(”则不是。您有一个由字符“(”、“)”和“?”组成的括号序列模式。您必须将每个字符“?”替换为括号,这样才能得到常规括号序列。

对于每个字符“?”给出了用“(”和“)”替换它的成本。在所有可能的变体中,您应该选择最便宜的。

输入

第一行包含偶数长度的非空模式,由字符“(”、“)”和“?”组成。其长度不超过5·104。接下来是m行,其中m是字符“?”的数量。在模式中。每行包含两个整数ai和bi(1≤ai,bi≤106),其中ai是替换第i个字符“?”的成本带左括号,bi - 带右括号。

输出

在第一行中打印最佳正则括号序列的成本,在第二行中打印所需的序列。

如果没有答案,则打印 -1。如果答案不唯一,请打印其中任何一个。

示例

输入 #1

(??)
1 2
2 8

输出 #1

4
()()