Optimal Common Subsequence

Given two strings $A$ and $B$, which consist of lowercase Latin letters and digits.

Find the string of the shortest length that includes strings $A$ and $B$ as subsequences and output its length. It is allowed for the strings $A$ and $B$ to appear with gaps in the desired string, but it is important that the sequence of characters of strings $A$ and $B$ is preserved in the desired string.

Input

The first line of the input contains the string $A$, the second line contains the string $B$.

The length of strings $A$ and $B$ does not exceed $5000$ characters.

Output

Output a single number – the length of the shortest string that includes strings $A$ and $B$.

Examples