Unbalanced Parentheses

Barry and Bruce are twin brothers. Bruce likes keeping his parenthetical sequences balanced. Barry would like to mess with Bruce by performing some operations on the sequence. Each operation is one of the following:

1. Change a single ( to a ) in the sequence.
2. Change a single ) to a ( in the sequence.

Bruce will attempt to rebalance the parenthetical sequence by performing the same operations. Bruce does not like tedium and will perform no more than $k$ operations to balance the sequence. A balanced parenthetical sequence is defined as:

1. The empty string.
2. $AB$, where $A$ and $B$ are both balanced parenthetical sequences.
3. $(A)$, where $A$ is a balanced parenthetical sequence.

Barry would like to disrupt the sequence to the point where it is impossible for Bruce to rebalance it in at most $k$ moves. Changing a position in the sequence requires effort, and the amount of effort varies by position. Some positions are even delightful to switch and require negative effort. Each position can be changed at most once.

Barry hates effort. Compute the minimum total effort Barry needs to ensure that Bruce cannot balance the sequence.

The input consists of a single test case. Note that your program may be run multiple times on different inputs.

The first line contains two integers $n$ and $k$, where $n$ ($1 \le n \le 10^5$) is the length of the sequence and $k$ ($0 \le k \le n$) is the maximum number of moves for Bruce.

The next line contains a single string of length $n$ consisting only of the characters ( and ). This string is not required to be balanced.

Each of the next $n$ lines contains a single integer $c$ ($-1000 \le c \le 1000$). The $i$-th of these integers is the effort of changing the $i$-th parenthesis.

Output a single integer: the minimum total effort that makes the string impossible for Bruce to balance. Barry may change no position at all, in which case the total effort is $0$. The answer can be negative.

If Bruce can always rebalance the string regardless of Barry's actions, print a single question mark (?).