ggg

#include<bits/stdc++.h>
using namespace std;
char a[2010],b[2010];
int d[2010];
int p,t;
int main(){
cin>>a+1>>b+1;
for(int j=0;j<=strlen(b+1);j++){
d[j]=j;
}
for(int i=1;i<=strlen(a+1);i++){
p=d[0];
d[0]=i;
for(int j=1;j<=strlen(b+1);j++){
t=d[j];
if(a[i]==b[j]){
d[j]=p;
}else{
d[j]=min(min(d[j],d[j-1]),p)+1;
}
p=t;
}
}
cout<<d[strlen(b+1)];
return 0;
}