CF3D Least Cost Bracket Sequence

这又是一个括号序列相关的问题。 如果在一个括号序列中插入加号和数字 $1$，能够得到一个合法的数学表达式，则称该括号序列为合法括号序列。例如，序列 “(())()” 、“()” 和 “(()(()))” 都是合法的，而 “)(” 、 “(()” 和 “(()))(” 都不是。现在你得到一个仅由 “(”、“)” 和 “?” 组成的括号序列模式。你需要将每一个 “?” 替换成括号，使得最终得到一个合法的括号序列。 对于每一个问号 “?”，给定其替换为 “(” 和 “)” 的花费。请你在所有可能的替换方式中，选择代价最小的合法序列。

第一行是一个不为空的括号序列模式，长度为偶数，仅包含 “(”、“)” 和 “?”，长度不超过 $5 \cdot 10^4$。 接下来有 $m$ 行，其中 $m$ 为模式中 “?” 的数量。每一行包含两个整数 $a_i$、$b_i$（$1 \leq a_i, b_i \leq 10^6$），其中 $a_i$ 表示将第 $i$ 个 “?” 替换为 “(” 的代价，$b_i$ 表示替换为 “)” 的代价。

第一行输出能得到的最小代价。 第二行输出相应的合法括号序列。 如果不存在合法的括号序列，输出 $-1$。如果存在多个解，输出任意一个即可。

由 ChatGPT 5 翻译