대회가 끝났으므로 답안을 제출할 수 있습니다. "믄제에서 열기"를 누르세요.

题目描述

$S,T$ 是由左括号"("，和右括号")"构成的字符串。

我们定义两个字符串 $S,T$ 的查重度为满足要求的最长字符串 $C$ 的长度。

$C$ 同时是 $S,T$ 的子序列，并且是括号串。

通过删除任意位置任意个字符（含零个），按顺序连接剩余部分得到的字符串称为原字符串的子序列。

我们定义满足以下条件的字符串为括号串。

1.空串是括号串。

2.如果 $A$ 是括号串，$(A)$ 是括号串。

3.如果 $A,B$ 都是括号串，$AB$ 是括号串。

输入格式

输入一行两个整数 $n,m$ 分别表示 $S,T$ 的长度。

接下来两行分别是字符串 $S,T$ 。

输出格式

一行一个整数表示两个字符串的查重度。

输入输出样例 #1

输入 #1

10 12
(()())(())
(()(()))()()

输出 #1

8

输入输出样例 #2

输入 #2

2 2
()
)(

输出 #2

0

说明/提示

样例一：最长公共子括号串是 "(()())()" 。

对于 $30\%$ 数据，$n,m \le 20$ 。

对于另外 $30\%$ 数据，$m \le 20$ 。

对于全部数据，$1 \le n,m \le 200$ 。