P16152 [ICPC 2017 NAIPC] Unbalanced Parentheses

Barry 和 Bruce 是双胞胎兄弟。Bruce 喜欢保持他的括号序列平衡。Barry 想通过对序列进行一些操作来干扰 Bruce。每次操作是以下之一： 1. 将序列中的一个 '(' 改为 ')'。 2. 将序列中的一个 ')' 改为 '('。 Bruce 会尝试通过执行相同的操作来重新平衡括号序列。Bruce 不喜欢繁琐的事情，他最多会进行 $k$ 次操作来使序列平衡。 平衡括号序列的定义如下： 1. 空字符串 2. $AB$，其中 $A$ 和 $B$ 都是平衡的括号序列 3. $(A)$，其中 $A$ 是平衡的括号序列 Barry 希望扰乱序列，使得 Bruce 无法在 $k$ 步内重新平衡该序列。改变序列中的某个位置需要付出努力，且不同位置的努力值不同。有些位置甚至令人愉悦地切换，需要负的努力值。每个位置最多只能改变一次。 Barry 讨厌付出努力，他想计算确保 Bruce 无法平衡该序列所需的最小努力值之和。

每个输入包含单个测试用例。请注意，你的程序可能会在不同输入上多次运行。输入的第一行包含两个整数 $n$ 和 $k$，其中 $n$（$1 \leq n \leq 10^5$）是序列的长度，$k$（$0 \leq k \leq n$）是 Bruce 的最大操作次数。 下一行包含一个长度为 $n$ 的字符串，仅由字符 '(' 和 ')' 组成。该字符串不一定是平衡的。 接下来的 $n$ 行，每行包含一个整数 $c$（$-1{,}000 \leq c \leq 1{,}000$），表示按顺序改变每个括号的成本。

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

翻译由 DeepSeek V3.2 完成