#include<bits/stdc++.h>
using namespace std;
const int N =2e3+10;
string a,b;
int n,m;
int dp[N][N];
int main(){
	cin>>a>>b;
	n=a.size(),m=b.size();
	a=" "+a,b=" "+b;
	memset(dp,0x3f,sizeof(dp));
	dp[1][1]=(!(a[1]==b[1]));
	dp[2][1]=min((!(a[2]==b[1]))+1,(!(a[1]==b[1]))+1);
	dp[1][2]=min((!(a[1]==b[2]))+1,(!(a[1]==b[1]))+1);
	for(int i=2;i<=n;i++){
		for(int j=2;j<=m;j++){
			if(a[i]==b[j]) dp[i][j]=min(dp[i][j],dp[i-1][j-1]);
			dp[i][j]=min(min(min(dp[i][j-1]+1,dp[i-1][j]+1),dp[i-1][j-1]+1),dp[i][j]);
		}
	}
	cout<<dp[n][m];
	return 0;
}

WA ON #3 #6