#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef vector<ii> vii;

const int  MOD=1000000007;
const int  INF= int(1e9);
const int  MAX =1007;
string a,b;
int n,m;
int dp[MAX][MAX];

int solve ( int n,int m) {
    if(dp[n][m] != -1) {
        return dp[n][m];
    }
    else if(m == 0) {
        return dp[n][m]=n;
    }
    else if(n == 0) {
        return dp[n][m]=m;
    }
    if (a[n-1] == b[m-1] ) {
        return dp[n][m]=solve(n-1,m-1);
    }
    dp[n][m] = 1 + min(  solve(n-1,m-1) , min ( solve(n-1,m) ,solve(n,m-1) ) );
    return dp[n][m];
}


int main()
{
    ios_base::sync_with_stdio(false);
    for(int i=0;i<MAX;i++) {
        for(int j=0;j<MAX;j++) {
            dp[i][j]=-1;
        }
    }
    cin>>a;
    cin>>b;
    n=a.size(),m=b.size();
    solve(n,m);
    cout<<dp[n][m]<<"\n";

    return 0;

}
#include <iostream>
#include <string>
#define int long long
//#define _DEBUG
using namespace std;
string sa, sb;
int T[1009][1009];
int solve(){
    int sal = sa.length(), sbl = sb.length();
    for(int a=0; a<=sal; a++){
        for(int b=0; b<=sbl; b++){
            if(a==0){
                T[a][b] = b;
            }else if(b==0){
                T[a][b] = a;
            }else{
                T[a][b] = 
                    min(min(T[a][b-1]+1, T[a-1][b]+1),
                    T[a-1][b-1]+((sa[a-1]==sb[b-1])?0:1));
            }
        }
    }
    return T[sal][sbl];
}
signed main(){
    while(cin >> sa >> sb){
        cout << solve() << endl;
    }
}
