题目描述

有 $\red{A=a1a2a3...am,B=b1b2b3...bn }$两个字符串$\red{(}$均为小写字母$\red{)}$现在要通过以下操作将 $\red{A}$ 或 $\red{A }$的一个后缀修改为 $\red{B：}$

$\red{1. }$删除 删除掉 $\red{A }$中的某一个字符。

$\red{2. }$添加 将某一个字符添加到 $\red{A }$中任意位置。

$\red{3. }$替换 将 $\red{A }$中某一字符替换为另一个。

求出最小操作次数。

输入格式

第一行为字符串 $\red{A}$。

第二行为字符串 $\red{B(}$长度均不超过 $\red{1000)}$。

输出格式

一个正整数，最小操作次数。

样例

输入样例

aaab
aabc

输出样例

1

提示

$\red{1 }$次操作 使用后缀 $\red{aab }$在末尾插入 $\red{c}$。