Lewin 和 Gan 有一个括号序列。不，那个词太笨拙了。好吧，再来一次：

给定一个括号序列。每个括号有 3 种颜色之一：青色（lime）、灰色（gray）和蓝色（blue），并且每个括号要么是左括号，要么是右括号。

你可以将某些括号从左括号改为右括号，反之亦然。你不能改变括号的顺序或颜色。你希望进行零次或多次修改，使得最终的序列满足以下条件：

1. 如果移除所有青色括号，剩余的括号构成一个合法的括号序列。
2. 如果移除所有灰色括号，剩余的括号构成一个合法的括号序列。

一个括号序列 $S$ 是合法的，如果它满足以下条件之一：

1. $S$ 为空。
2. $S = XY$，其中 $X$ 和 $Y$ 均为非空的合法括号序列。
3. $S = (X)$，其中 $X$ 是一个合法括号序列。注意，起始的左括号和结尾的右括号可以有不同的颜色。

请问是否可能实现这一目标？如果可以，最少需要进行多少次修改？

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 6000$)，表示括号序列的长度。 第二行包含一个长度为 $n$ 的字符串 $s$，由字符 "(" 和 ")" 组成，表示括号序列。 第三行包含 $n$ 个整数 $c_i$ ($0 \le c_i \le 2$)。$c_i$ 表示第 $i$ 个括号的颜色。$0$ 代表青色，$1$ 代表灰色，$2$ 代表蓝色。

输出格式

输出一个整数，表示如果满足条件，最少需要进行的修改次数；否则输出 $-1$。

样例

样例输入 1

5
))))(
0 1 2 2 2

样例输出 1

4

样例输入 2

3
()(
0 2 1

样例输出 2

-1

样例输入 3

6
(()())
0 0 0 0 0 0

样例输出 3

0

说明

在第一个样例中，一个可能的最终序列是 (()()。