By Gabriel Duarte, UFF Brazil
Dabriel is playing with her two wonderful strings, and when doing some operations with them, she realized one thing:
there is always a third string that contains its other two strings as a subsequence.
A subsequence is formed by removing some characters, and the remainder remains in the same relative position. For example: The string 'casa' contains as a substring the string 'cs', but does not contain the string 'ac'.
After some time analyzing these properties, Dabriel realized that to generate the third string it was enough to concatenate the other two, a very trivial thing. Therefore, he asked for his help to determine the size of the smallest string that has both as a substring.
The first line contains the string A (1 ≤ |A| ≤ 1000), and the second line contains the string B (1 ≤ |B| ≤ 1000). They are formed by only the small letters of the alphabet.
Print the size of the smallest string that has strings A and B as subsequences.
Input Samples | Output Samples |
casa |
6 |
bola |
5 |