Minimum cost to make two words equal P24879

We are given two words s and t made up of only lowercase letters, and we must make them equal. We can only perform two kind of operations, as many times as needed: Remove a letter, with cost 3, and duplicate a letter, with cost 2. What is the minimum possible cost?

For example, for s= “aaba” and t= “abb” the minimum cost is 7, which corresponds to duplicating the ‘b’ and removing the last ‘a’ of s, and duplicating the ‘a’ of t.

Input

Input consists of several cases with s and t, both with between 1 and 1000 letters.

Output

For every case, print the minimum cost to make the two words equal.