Construct the String

4000ms

524288K

Description:

Let's denote the function $$$f(s)$$$ that takes a string $$$s$$$ consisting of lowercase Latin letters and dots, and returns a string consisting of lowercase Latin letters as follows:

let $$$r$$$ be an empty string;
process the characters of $$$s$$$ from left to right. For each character $$$c$$$, do the following: if $$$c$$$ is a lowercase Latin letter, append $$$c$$$ at the end of the string $$$r$$$; otherwise, delete the last character from $$$r$$$ (if $$$r$$$ is empty before deleting the last character — the function crashes);
return $$$r$$$ as the result of the function.

You are given two strings $$$s$$$ and $$$t$$$. You have to delete the minimum possible number of characters from $$$s$$$ so that $$$f(s) = t$$$ (and the function does not crash). Note that you aren't allowed to insert new characters into $$$s$$$ or reorder the existing ones.

Input:

The input consists of two lines: the first one contains $$$s$$$ — a string consisting of lowercase Latin letters and dots, the second one contains $$$t$$$ — a string consisting of lowercase Latin letters ($$$1 \le |t| \le |s| \le 10000$$$).

Additional constraint on the input: it is possible to remove some number of characters from $$$s$$$ so that $$$f(s) = t$$$.

Output:

Print one integer — the minimum possible number of characters you have to delete from $$$s$$$ so $$$f(s)$$$ does not crash and returns $$$t$$$ as the result of the function.

Sample Input:

a.ba.b.
abb

Sample Output:

Sample Input:

.bbac..a.c.cd
bacd

Sample Output:

Sample Input:

c..code..c...o.d.de
code

Sample Output:

Informação

Provedor Codeforces

Código CF1366G