B. Whispers of the Old Gods
time limit per test
8 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Legend has it that the Old Gods' voices are dread whispers that no mere mortal can hope to resist. And now, the time of their awakening draws near. Will you head their whispers at your ear?

We may represent a whisper by a sequence of digits. And surprisingly, the whispers of the Old Gods can be characterized by a regular expression (<regex>). The syntax of a regular expression is shown below (in Backus-Naur form):


<regex> ::= <regex> <regex>
          | <regex> "|" <regex>
          | <regex> "+"
          | <atomic-regex>

<atomic-regex> ::= <digit>
                 | "[" <digit-sequence> "]"
                 | "(" <regex> ")"

where <digit> is any single digit (0, 1, ..., 9) and <digit-sequence> is any nonempty sequence of digits. In case of any ambiguity, the positive closure (<regex> "+") has the highest precedence, which is followed by the concatenation (<regex> <regex>), and the alternation (<regex> "|" <regex>) has the lowest precedence. For example, the regular expression 1|23+ should be parsed as (1|(2(3+))).

Every regular expression $$$R$$$ recognizes a set of digit strings, denoted $$$L(R)$$$, which is defined as follows:

  • $$$L(R_1 R_2) = \{s \circ t | s \in L(R_1), t \in L(R_2) \}$$$, where $$$R_1$$$, $$$R_2$$$ are regular expressions and $$$\circ$$$ means string concatenation;
  • $$$L(R_1 | R_2) = L(R_1) \cup L(R_2) $$$, where $$$R_1$$$, $$$R_2$$$ are regular expressions;
  • $$$L(R +) = \bigcup_{i=1}^{\infty} \{s^i | s \in L(R) \}$$$, where $$$s^i = s \circ s^{i-1}$$$ $$$(i \gt 1)$$$ and $$$s^1 = s$$$;
  • the regular expression $$$d$$$ (where $$$d$$$ is any single digit) recognizes the single digit $$$d$$$;
  • the regular expression $$$[s]$$$ (where $$$s$$$ is any nonempty sequence of digits) recognizes any single digit appearing in $$$s$$$;
  • parenthesizing a regular expression doesn't change the set it recognizes, i.e., $$$L((R)) = L(R)$$$.

Given a regular expression describing the whispers of the Old Gods and a whisper you heard last night, you wonder how close is the whisper you heard to the Old Gods'. Specifically, you want to know the minimum number of changes to make it recognized by the regular expression. There are three kinds of changes to the whisper:

  • inserting a single digit at any position;
  • removing any single digit;
  • replacing any single digit with any other digit.

For example, let the regular expression be (5|6+)[12]3+, and the sequence of digits you've heard be 4334. One possible way to make minimum number of changes to make the digit sequence recognized by the regular expression is 4334 -> 54334 -> 52334 -> 5233.

Input

The input contains two lines.

The first line of the input is the regular expression $$$R$$$ characterizing the whispers of the Old Gods, which contains at most $$$5\,000$$$ characters. The regular expression is syntactically correct and contains no character other than digits, |, [, ], (, ), and +.

The second line is a nonempty digital sequence with at most $$$10^4$$$ digits, denoting the whisper you've heard.

Output

Print a single integer, denoting the minimum number of changes you could make to the whisper, such that it can be recognized by the regular expression.

Examples
Input
(5|6+)[12]3+
4334
Output
3
Input
[12](3+|4+)+
2345
Output
1
Input
(234|25)+
2442342523535
Output
3