不平衡的括号 - 题目

Barry 和 Bruce 是双胞胎兄弟。Bruce 喜欢保持括号序列的平衡。Barry 想要通过对序列执行一些操作来捉弄 Bruce。每种操作如下：

Bruce 会尝试通过执行相同的操作来重新平衡括号序列。Bruce 不喜欢繁琐的工作，因此他最多只会执行 $k$ 次操作来平衡序列。

平衡括号序列的定义如下： 1. 空字符串。 2. $AB$，其中 $A$ 和 $B$ 都是平衡括号序列。 3. $(A)$，其中 $A$ 是一个平衡括号序列。

Barry 想要破坏该序列，使得 Bruce 无法在 $k$ 次移动内将其平衡。改变序列中某些位置的括号需要付出努力，且不同位置所需的努力程度各不相同。有些位置甚至非常容易切换，需要负的努力值。每个位置最多只能被改变一次。

Barry 讨厌付出努力，他想计算出确保 Bruce 无法平衡序列所需的最小努力总和。

输入包含单个测试用例。注意，你的程序可能会在不同的输入上运行多次。输入的第一行包含两个整数 $n$ 和 $k$，其中 $n$ ($1 \le n \le 10^5$) 是序列的长度，$k$ ($0 \le k \le n$) 是 Bruce 最多可以执行的移动次数。

下一行包含一个长度为 $n$ 的字符串，仅由字符 '(' 和 ')' 组成。该字符串不一定需要是平衡的。

接下来的 $n$ 行，每行包含一个整数 $c$ ($-1,000 \le c \le 1,000$)，表示按顺序改变每个括号所需的代价。

输出一个整数，表示使得 Bruce 无法平衡字符串所需的最小努力总和。如果无论 Barry 如何操作，Bruce 总能平衡该字符串，则输出一个问号 ('?')。

QOJ.ac