2761: T5-括号
内存限制：128 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：6
解决：1
题目描述
现在给你一个括号序列。每个括号要么是左括号，要么是右括号。所有括号都被染了颜色，每个括号被染了以下 $3$ 种颜色中的一种：红色、绿色和蓝色。
你现在可以把某些位置的括号从左括号变成右括号，或者从右括号变成左括号。你不允许改变括号的排列顺序，也不允许改变括号的颜色。现在，你可以用零次或多次的修改操作，使得最终的括号序列同时满足以下两个条件：
1. 如果去掉所有的红色括号，剩下的括号构成一个合法的括号序列。
2. 如果去掉所有的绿色括号，剩下的括号构成一个合法的括号序列。
一个括号序列 $S$ 是合法的当且仅当它满足条件之一：
1. $S$ 为空。
2. 存在两个合法的括号序列 $X, Y$ ，使得 $S = XY$ 。
3. 存在一个合法的括号序列 $X$ ，使得 $S = (X)$ 。请注意，在这种情况下，最左的左括号和最右的右括号\emph{可以}是不同颜色的。
问是否存在一种修改方案？若存在，最少的修改次数是多少？
你现在可以把某些位置的括号从左括号变成右括号，或者从右括号变成左括号。你不允许改变括号的排列顺序，也不允许改变括号的颜色。现在，你可以用零次或多次的修改操作，使得最终的括号序列同时满足以下两个条件：
1. 如果去掉所有的红色括号，剩下的括号构成一个合法的括号序列。
2. 如果去掉所有的绿色括号，剩下的括号构成一个合法的括号序列。
一个括号序列 $S$ 是合法的当且仅当它满足条件之一：
1. $S$ 为空。
2. 存在两个合法的括号序列 $X, Y$ ，使得 $S = XY$ 。
3. 存在一个合法的括号序列 $X$ ，使得 $S = (X)$ 。请注意，在这种情况下，最左的左括号和最右的右括号\emph{可以}是不同颜色的。
问是否存在一种修改方案？若存在，最少的修改次数是多少？
输入
第一行包含一个正整数 $n$ ，表示括号序列的长度。
第二行包含一个只包含 '(' 和 ')' 的字符串 $s$ ，表示给定的括号序列。
第三行包含 $n$ 个整数 $c_i (0 \leq c_i \leq 2)$ 。 $c_i$ 表示第 $i$ 个括号的颜色。 $0$ 表示红色， $1$ 表示绿色，$2$ 表示蓝色。
第二行包含一个只包含 '(' 和 ')' 的字符串 $s$ ，表示给定的括号序列。
第三行包含 $n$ 个整数 $c_i (0 \leq c_i \leq 2)$ 。 $c_i$ 表示第 $i$ 个括号的颜色。 $0$ 表示红色， $1$ 表示绿色，$2$ 表示蓝色。
输出
如果存在一种修改方案，输出一个整数表示最少的修改次数。否则输出 -1 。
样例输入 复制
5
))))(
0 1 2 2 2样例输出 复制
4提示
```input2
3
()(
0 2 1
```
```output2
-1
```
```input3
6
(()())
0 0 0 0 0 0
```
```output3
0
```
# Limitation
子任务1（5%）： $n \leq 20$ 。
子任务2（10%）： $n \leq 400$ 。
子任务3（15%）： $n \leq 6000, c_i = 2$ 。
子任务4（20%）： $n \leq 6000, c_i \neq 1$ 。
子任务5（50%）： $n \leq 6000$ 。
对于所有数据， $1 \leq n \leq 6000$，$0 \leq c_i \leq 2$ 。
3
()(
0 2 1
```
```output2
-1
```
```input3
6
(()())
0 0 0 0 0 0
```
```output3
0
```
# Limitation
子任务1（5%）： $n \leq 20$ 。
子任务2（10%）： $n \leq 400$ 。
子任务3（15%）： $n \leq 6000, c_i = 2$ 。
子任务4（20%）： $n \leq 6000, c_i \neq 1$ 。
子任务5（50%）： $n \leq 6000$ 。
对于所有数据， $1 \leq n \leq 6000$，$0 \leq c_i \leq 2$ 。