균형 잡힌 무지개 괄호 수열

르윈과 간은 괄호 수열을 하나 가지고 있다. 아니, 이 단어는 너무 어색하다. 다시 한 번 말한다:

괄호 수열이 주어진다. 각 괄호는 라임, 회색, 파랑 중 하나의 색을 가지며, 여는 괄호이거나 닫는 괄호이다.

일부 괄호를 여는 괄호에서 닫는 괄호로, 또는 그 반대로 바꿀 수 있다. 괄호의 순서와 색은 바꿀 수 없다. 다음 두 조건을 만족하도록 0번 이상 바꾸려고 한다.

1. 라임 괄호를 모두 제거했을 때 남은 괄호가 균형 잡힌 괄호 수열이 된다.
2. 회색 괄호를 모두 제거했을 때 남은 괄호가 균형 잡힌 괄호 수열이 된다.

괄호 수열 $S$는 다음 조건 중 하나를 만족하면 균형 잡힌 괄호 수열이다.

1. $S$는 비어 있다.
2. $S = XY$이고, $X$와 $Y$는 모두 비어 있지 않은 균형 잡힌 괄호 수열이다.
3. $S = (X)$이고, $X$는 균형 잡힌 괄호 수열이다. 맨 앞의 여는 괄호와 맨 뒤의 닫는 괄호는 색이 다를 수 있다.

이것이 가능한가? 가능하다면 필요한 변경 횟수의 최솟값은 얼마인가?

첫째 줄에 괄호 수열의 길이 $n$ ($1 \leq n \leq 6000$)이 주어진다.

둘째 줄에 길이가 $n$인 문자열 $s$가 주어진다. $s$는 "("와 ")"로만 이루어진 괄호 수열이다.

셋째 줄에 정수 $n$개 $c_i$ ($0 \leq c_i \leq 2$)가 주어진다. $c_i$는 $i$번째 괄호의 색이다. 0은 라임, 1은 회색, 2는 파랑에 대응한다.

조건을 만족하도록 만들 수 있으면 필요한 변경 횟수의 최솟값을 출력한다. 만들 수 없으면 -1을 출력한다.

첫 번째 예제에서 가능한 결과 수열은 (()()이다.