You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

八云紫拥有操控境界程度的能力。作为其式神的八云蓝，同样拥有一定程度的操作境界的能力，而作为八云蓝的式神橙，却因为功力尚且不足，而无法对境界进行过多的干预了。

于是八云蓝打算教教橙，境界的用法。境界可以被抽象成一层一层的括号，操作境界本质上就是对括号序列进行修改。由于橙的能力尚且不足，因此只能进行一些简单的境界的建立与摧毁。

尽管如此，通过简单的操作，亦可以把一个境界转换为另外一个境界。为了给橙作为练习，蓝找来了两个境界的范本。将其中一个境界转换为另外一个境界的难度，就是橙需要施用能力的最小次数。但是由于境界实在太长，蓝决定写一个程序（？）来帮帮她计算出境界的难度。

题目描述

境界可以被抽象为由圆括号组成的括号序列。现做出如下定义：

• 定义 $D_i$ 为嵌套括号序列。其中 $D_0$ 为零阶嵌套括号序列，被定义为单组括号 $\verb!()!$；而 $D_k$ 则为 $k$ 阶嵌套括号序列（$k \geq 1$）定义为 $\verb!(!D_{k-1}\verb!)!$，即在 $D_{k-1}$ 的外层增添了一层括号。
• 定义 $F_i$ 为平铺括号序列。其中 $F_0$ 为零阶平铺括号序列，被定义为单组括号 $\verb!()!$；而 $F_k$ 则为 $k$ 阶平铺括号序列（$k \geq 1$），定义为 $\verb!()!F_{k-1}$，即在 $F_{k-1}$ 的左侧增添了一对括号。

例如，$\verb!((()))!$ 为 $D_2$，$\verb!()()()()!$ 为 $F_{3}$。

现在蓝给出了两个长度为 $n$ 的合法括号序列 $A$ 和 $B$。橙可以用以下操作对序列 $A$ 进行变换：

• 选择任意非负整数 $k$，选择括号序列的一个子串满足其为一个 $k$ 阶嵌套括号序列，然后将其变为 $k$ 阶平铺括号序列。
• 选择任意非负整数 $k$，选择括号序列的一个子串满足其为一个 $k$ 阶平铺括号序列，然后将其变为 $k$ 阶嵌套括号序列。

提示说明处有「合法括号序列」与「子串」的定义。

现在需要求出将序列 $A$ 变换为序列 $B$ 所需的最少操作数。可以证明，总存在一种操作方案能将序列 $A$ 变换为序列 $B$。

输入格式

• 第一行共有一个整数 $n$，表示 $A$ 与 $B$ 括号序列的长度。
• 接下来一行，共有 $n$ 个字符，描述括号序列 $A$。保证序列 $A$ 合法。
• 接下来一行，共有 $n$ 个字符，描述括号序列 $B$。保证序列 $B$ 合法。

输出格式

• 共一行，一个整数，表示将 $A$ 转换为 $B$ 需要的最少步数（可能为 $0$，也就是不进行任何操作）。

样例 #1

样例输入 #1

14
((()())(()()))
()()()()()()()

样例输出 #1

6

样例 #2

样例输入 #2

14
((()())(()()))
(()())(()())()

样例输出 #2

10

提示

样例 $3$ 见下发的附件 $\textbf{\textit{border3.in/border3.ans}}$。 样例 $4$ 见下发的附件 $\textbf{\textit{border4.in/border4.ans}}$。满足特殊性质 $\text{A}$（见下文）。 样例 $5$ 见下发的附件 $\textbf{\textit{border5.in/border5.ans}}$。

样例 1 解释

• 第一步：$\texttt{((\underline{()()})(()()))}\to\texttt{((\underline{(())})(()()))}$。
• 第二步：$\texttt{(((()))(\underline{()()}))}\to\texttt{(((()))(\underline{(())}))}$。
• 第三步：$\texttt{(((()))\underline{((()))})}\to\texttt{(((()))\underline{()()()})}$。
• 第四步：$\texttt{(\underline{((()))}()()())}\to\texttt{(\underline{()()()}()()())}$。
• 第五步：$\texttt{(\underline{()()()()()()})}\to\texttt{(\underline{(((((())))))})}$。
• 第六步：$\texttt{\underline{((((((()))))))}}\to\texttt{\underline{()()()()()()()}}$。

可以证明，不存在更短的方案。

提示

合法括号序列通过这样一个形式定义：

• $\verb!()!$ 是合法括号序列。
• 若 $A$ 是合法括号序列，那么 $\verb!(!A\verb!)!$ 是合法括号序列。
• 若 $A,B$ 均为合法括号序列，那么 $AB$ 是合法括号序列。

我们称 $A$ 是 $B$ 的子串，当且仅当删除 $B$ 开头若干个字符（可以不删除），再删除 $B$ 末尾若干个字符（可以不删除），剩下来的字符序列与 $A$ 完全相同。

数据范围及约定

本题共有 $20$ 个测试点，每个测试点 $5$ 分。最终分数为所有测试点分数之和。

$$\def\arraystretch{1.5} \begin{array}{|c|c|c|}\hline \textbf{Task} & \bm{n\le } & \textbf{特殊性质} \cr\hline 1\sim 4 & 10 & - \cr\hline 5\sim 7 & 2\times 10^3 & \text{A} \cr\hline 8\sim 10 & 2\times 10^3 & - \cr\hline 11\sim 15 & 10^6 & \text{A} \cr\hline 16\sim 20 & 10^6 & - \cr\hline \end{array} $$

特殊性质 $\textbf{A}$：保证 $B$ 是 $(n\div 2-1)$ 阶平铺括号序列。

友情提醒

考虑到选手可能会用不同的方式进行字符串的读入，这里保证输入文件每行末尾没有多余空格，并且每行都以 \n 结尾（也就是说，不会出现多余的 \r）。