RNA

RNA is an important molecule in the body. The structure of an RNA molecule is written as a pair $(S, P)$ that satisfies the following four conditions.

1. $S = s_1 s_2 \dots s_n$ and $P = p_1 p_2 \dots p_n$ for some positive integer $n \le 450$.
2. Each element $s_i$ of $S$ is one of the letters A, C, G, U.
3. Each element $p_i$ of $P$ is an asterisk, a left parenthesis, or a right parenthesis.
4. $P$ is a balanced parenthesis sequence. That means that after all asterisks are ignored, each left parenthesis is matched by exactly one right parenthesis after it, and each right parenthesis is matched by exactly one left parenthesis before it.

Here are two RNA structures, $A_1 = (S_1, P_1)$ on the left and $A_2 = (S_2, P_2)$ on the right.

ACCCGAACUU   AAUAUCCCGAAU
((**)*(*))   *(**)(**)*()

For two RNA structures $A = (S, P)$ and $A' = (S', P')$, we call $A'$ a substructure of $A$ if there are integers $i \le j$ with $S' = s_i \dots s_j$ and $P' = p_i \dots p_j$. Since $A'$ is itself an RNA structure, the parentheses of $P'$ must be balanced too. For example, $A_3 = (S_3, P_3)$

CCCG
(**)

is a substructure of $A_1$, while $A_4 = (S_4, P_4)$

ACCCGAACU
((**)*(*)

is not a substructure of $A_1$, because the parentheses of $P_4$ are not balanced.

For two RNA structures $X$ and $Y$, a structure $Z$ that is a substructure of both is called a common substructure of $X$ and $Y$. A longest common substructure is a common substructure of maximum length.

For the $A_1$ and $A_2$ above, the longest common substructure has length 5 and is

CCCGA
(**)*

The following is not a common substructure of $A_1$ and $A_2$, because its parentheses are not balanced.

CCCGAA
(**)*(

You are given two RNA structures of length at most 450. Report the length of a longest common substructure.

The input consists of four lines. The first line is the base sequence $S$ of the first RNA and the second line is its parenthesis sequence $P$. The third line is the base sequence $S'$ of the second RNA and the fourth line is its parenthesis sequence $P'$.

Within one RNA the base sequence and the parenthesis sequence have the same length, which is between 1 and 450.

Print the length of a longest common substructure on one line. Print 0 if there is no common substructure at all.