Bracket Sequence Transformation

A bracket sequence can be abstracted as a sequence composed only of round brackets. In this problem we define two families of special bracket sequences:

• For each non‐negative integer k, define the kth-order nested sequence D_k recursively as follows:
  • D₀ is defined as ().
  • For k ≥ 1, D_k is defined as (Dk-1). In other words, D_k is obtained by adding an outer pair of parentheses to D_k-1.
  For example, ((())) is D₂ because it equals ((())) = ( (()) ).
• For each non‐negative integer k, define the kth-order flat sequence F_k recursively as follows:
  • F₀ is defined as ().
  • For k ≥ 1, F_k is defined as ()Fk-1, i.e. by concatenating a pair () to the left of F_k-1.
  For example, ()()()() is F₃ (note that F₃ has 4 pairs of brackets).

Now, you are given two legal bracket sequences A and B of equal length n. An operation is defined as follows:

• Choose any non-negative integer k and select a substring of the sequence which is exactly a kth-order nested sequence (D_k). Then convert this substring into the corresponding kth-order flat sequence (F_k).
• Or, choose any non-negative integer k and select a substring which is exactly a kth-order flat sequence (F_k). Then convert this substring into the corresponding kth-order nested sequence (D_k).

Notes:

• A legal bracket sequence is one that is balanced.
• A substring denotes a contiguous segment of the sequence.

It can be proven that it is always possible to transform A into B using a sequence of the above operations. Your task is to compute the minimum number of operations needed to transform A into B.

Input format: Two lines containing the legal bracket sequences A and B respectively.

Output format: A single integer representing the minimum number of operations required.

inputFormat

The input consists of two lines. The first line contains the bracket sequence A and the second line contains the bracket sequence B. Both sequences have the same even length n and are legal (balanced) bracket sequences.

outputFormat

Output a single integer indicating the minimum number of operations required to transform A into B.

sample

((()))
()()()

1