#include<bits/stdc++.h>
using namespace std;
// #define int long long
#define i(n) int n;cin>>n;for(int i=0;i<(n);i++)cin>>arr[i];
#define f(arr,n) int arr[n]={0}; for(int i=0;i<n;i++)cin>>arr[i];
#define w(t) int t;cin>>t;while(t--)
#define c(n) for(int i=1;i<=n;i++)cout<<arr[i]<<" ";
#define yes  cout<<"YES"<<endl
#define no   cout<<"NO"<<endl
string a,b;
const int MAXX = 1e9 + 7;
int dp[5001][5001] = {0};
//Edit Distance converts String A to String B in minimum Steps
int editDistance(string A,string B,int i,int j){
   if(i==A.length() or j==B.length()){
       return max((int)B.length()-j,(int)A.length()-i);
   }
   if(dp[i][j]!=-1){
       return dp[i][j];
   }


     if(A[i]==B[j]){
    dp[i][j] = editDistance(A,B,i+1,j+1);
   return dp[i][j];
   }
   else{
    //Add One Character to String A
   int op1 = 1+editDistance(A,B,i,j+1);
   //Remove One Character from String A
   int op2 = 1+editDistance(A,B,i+1,j);
   //Replace Character
   int op3 = 1+editDistance(A,B,i+1,j+1);
   int ans = min(op1,min(op2,op3));
   dp[i][j] = ans;
   return ans;
   }
 
}
signed main(){
    cin>>a>>b;
    for (int i = 0; i <= a.length(); i++)
    {
       for (int j = 0; j <= b.length(); j++)
       {
           dp[i][j] = -1;
       }
       
    }
    
    cout<<editDistance(a,b,0,0)<<endl;
   return 0;
}