Get Minimum Conflicts (Merge Branches)

Interleave two strings while keeping the original order of the characters within each string. An inversion is a pair of indices where the earlier character is strictly greater than the later one; find the minimum number of inversions after merging. For the source's zc and qd, the optimum under this definition is 4, not 2.

输入格式

Two lines of lowercase strings, each of length 1..1000.

输出格式

Output a single integer answer.

样例 1

输入：

zc
qd

输出：

4

样例 2

输入：

a
b

输出：

0

样例 3

输入：

ba
a

输出：

1

样例说明

Example 1: merging into qdzc gives four inversions (q,d), (q,c), (d,c), (z,c), which is optimal; the source's 2 does not match the all-index-pairs definition. Example 2: merging into ab gives 0. Example 3: merging into aba gives only one inversion, (b,a).