传说古神的低语是凡人无法抗拒的恐怖耳语。现在，他们苏醒的时间临近了。你是否听到了耳边的低语？

我们可以用数字序列来表示一段低语。令人惊讶的是，古神的低语可以用正则表达式（<regex>）来刻画。正则表达式的语法（采用巴科斯范式）如下所示：

::= | "|" | "+" |

::= | "[" "]" | "(" ")"

其中 <digit> 是任意单个数字（0, 1, ..., 9），<digit-sequence> 是任意非空数字序列。若存在歧义，正闭包（<regex> "+"）的优先级最高，其次是连接（<regex> <regex>），交替（<regex> "|" <regex>）的优先级最低。例如，正则表达式 1|23+ 应解析为 (1|(2(3+)))。

每个正则表达式 $R$ 识别一个数字字符串集合，记作 $L(R)$，定义如下：

• $L(R_1R_2) = \{s \circ t|s \in L(R_1), t \in L(R_2)\}$，其中 $R_1, R_2$ 为正则表达式，$\circ$ 表示字符串连接；
• $L(R_1|R_2) = L(R_1) \cup L(R_2)$，其中 $R_1, R_2$ 为正则表达式；
• $L(R+) = \bigcup_{i=1}^{\infty}\{s^i|s \in L(R)\}$，其中 $s^i = s \circ s^{i-1} (i > 1)$ 且 $s^1 = s$；
• 正则表达式 $d$（$d$ 为任意单个数字）识别单个数字 $d$；
• 正则表达式 $[s]$（$s$ 为任意非空数字序列）识别 $s$ 中出现的任意单个数字；
• 给正则表达式加上括号不会改变其识别的集合，即 $L((R)) = L(R)$。

给定一个描述古神低语的正则表达式和你昨晚听到的低语，你想知道你听到的低语与古神的低语有多接近。具体来说，你想要知道将你听到的低语修改为能被该正则表达式识别的字符串所需的最少修改次数。修改方式有三种：

• 在任意位置插入一个数字；
• 删除任意一个数字；
• 将任意一个数字替换为其他数字。

例如，假设正则表达式为 (5|6+)[12]3+，你听到的数字序列为 4334。将其修改为能被该正则表达式识别的序列的一种最少修改次数的方法是 4334 -> 54334 -> 52334 -> 5233。

输入格式

输入包含两行。

第一行是刻画古神低语的正则表达式 $R$，长度不超过 $5\,000$ 个字符。该正则表达式语法正确，且仅包含数字、|、[、]、(、) 和 +。

第二行是一个非空数字序列，长度不超过 $10^4$ 位，表示你听到的低语。

输出格式

输出一个整数，表示为了使该低语能被正则表达式识别，所需的最少修改次数。

样例

样例输入 1

(5|6+)[12]3+
4334

样例输出 1

3

样例输入 2

[12](3+|4+)+
2345

样例输出 2

1

样例输入 3

(234|25)+
2442342523535

样例输出 3

3