불균형 괄호

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

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

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

1. 빈 문자열
2. $A$와 $B$가 모두 균형 잡힌 괄호 문자열일 때 $AB$
3. $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$이다. 답은 음수일 수도 있다.

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