Minimum Merge Conflicts

Merge two lowercase strings while keeping the internal relative order of each original string, and minimize the number of pairs i<j in the merged string with s[i]>s[j]. Inversions within the same original string also count; equal characters do not.

输入格式

The two lines contain primary and secondary; the original bounds are 1≤length≤1000 for both, with lowercase letters only.

输出格式

Output a single integer, the answer.

样例 1

输入：

zc
d

输出：

2

样例 2

输入：

dae
add

输出：

1

样例 3

输入：

aa
aa

输出：

0

样例说明

The answers are 2, 1 and 0. The second example can be merged into adadde. Counting only cross-string inversions, as the source does, would undercount the first example as 1; the adddae shown in the source is also not an optimal arrangement for the second example.