불균형 괄호

문제

배리와 브루스는 쌍둥이 형제다. 브루스는 괄호 문자열이 균형 잡혀 있는 것을 좋아한다. 배리는 문자열에 몇 가지 연산을 해서 브루스를 골탕 먹이려고 한다. 각 연산은 다음 중 하나다.

문자열의 ( 하나를 )로 바꾼다.
문자열의 ) 하나를 (로 바꾼다.

브루스는 같은 연산으로 괄호 문자열의 균형을 다시 맞추려고 한다. 브루스는 지루한 일을 싫어해서 균형을 맞추는 데 연산을 최대 $k$ 번까지만 한다. 균형 잡힌 괄호 문자열은 다음과 같이 정의한다.

빈 문자열
$A$ 와 $B$ 가 모두 균형 잡힌 괄호 문자열일 때 $AB$
$A$ 가 균형 잡힌 괄호 문자열일 때 $(A)$

배리는 브루스가 $k$ 번 이하의 연산으로는 균형을 맞출 수 없을 때까지 문자열을 망가뜨리려고 한다. 문자열의 한 위치를 바꾸려면 노력이 들고, 드는 노력은 위치마다 다르다. 어떤 위치는 바꾸는 일이 즐거워서 노력이 음수이기도 하다. 각 위치는 최대 한 번만 바꿀 수 있다.

배리는 노력을 싫어한다. 브루스가 문자열의 균형을 맞출 수 없게 만드는 데 필요한 노력 합의 최솟값을 구하라.

입력

입력은 테스트 케이스 하나로 이루어진다. 프로그램은 서로 다른 입력으로 여러 번 실행될 수 있다.

첫째 줄에 두 정수 $n$ 과 $k$ 가 주어진다. $n$ ( $1 \le n \le 10^5$ )은 문자열의 길이이고, $k$ ( $0 \le k \le n$ )는 브루스가 할 수 있는 연산의 최대 횟수다.

둘째 줄에 (와 )로만 이루어진 길이 $n$ 의 문자열이 주어진다. 이 문자열은 균형 잡혀 있지 않을 수도 있다.

다음 $n$ 개의 줄에 정수 $c$ ( $-1000 \le c \le 1000$ )가 하나씩 주어진다. $i$ 번째 정수는 문자열의 $i$ 번째 괄호를 바꾸는 데 드는 노력이다.

출력

브루스가 문자열의 균형을 맞출 수 없게 만드는 데 필요한 노력 합의 최솟값을 정수 하나로 출력한다. 배리는 아무 위치도 바꾸지 않을 수 있고, 그때 노력의 합은 $0$ 이다. 답은 음수일 수도 있다.

배리가 무엇을 하든 브루스가 항상 균형을 다시 맞출 수 있다면 물음표 하나(?)를 출력한다.