English Problem Statement

蔡德仁有一个长度为 $n$ 的三色括号序列，每个括号被染成了红绿蓝三种颜色之一。

她可以对序列上的任何一个括号进行操作，单次操作可以让左括号变成右括号，或者让右括号变成左括号。括号的颜色不能修改。

她的目标是，操作最少的次数使整个序列同时满足如下条件：

• 整个序列是一个合法括号序列。
• 所有不是红色的括号组成的子序列是一个合法括号序列。
• 所有不是蓝色的括号组成的子序列是一个合法括号序列。
• 所有不是绿色的括号组成的子序列是一个合法括号序列。

你能帮她算出最小的操作次数吗？

注：合法括号序列的定义如下：

• 合法括号序列是一个只能包含 $($ 和 $)$ 的字符串
• 空串是合法括号序列
• 两个合法括号序列 $A,B$ 前后拼接 $AB$ 是合法括号序列
• 合法括号序列 $A$ 最外面增加一对括号 $(A)$ 是合法括号序列
• 一个字符串是合法括号序列当且仅当它可以通过以上几条在有限步内构造出来

输入格式

第一行一个长度为 $n$ 的括号序列 $s$。

第二行一个长度为 $n$ 的数字串 $a$。

第 $i$ 个数 $a_i$ 是 $1,2,3$ 分别代表括号序列中的第 $i$ 个字符 $s_i$ 的颜色是红、绿、蓝。

输出格式

一行一个整数，让序列满足条件需要的最小的操作次数。

样例

样例1

input

)())(((()(
2211113311

output

5

可以证明，一个最好的方法是将括号序列变成 ()()((()))。

样例2

input

))()))((()(()((()()))((())(()))(())))((()(())()())
32233212132212131113132123131122331233321133231223

output

7

可以证明，一个最好的方法是将括号序列变成 (((())((()(((((()()))((())(()))(())))(())(()))))))。

更多样例

见附加文件。

数据范围与提示

对于所有数据：$1\le n\le {10}^7,a_i\in \{1,2,3\}$，保证每种颜色的括号个数都是偶数。

本题采用子任务捆绑测试。

时间限制：$2\mathtt{\text{s}}$

空间限制：$512\mathtt{\text{MB}}$