#include<bits/stdc++.h>
#define ll long long
#define N ((int)6e4 + 5)
#define MOD ((int)1e9 + 7)
#define MAX ((int)1e9 + 7)
#define MAXL ((ll)1e18 + 7)
#define MAXP ((int)1e3 + 7)
#define thr 1e-8
#define pi acos(-1)  /// pi = acos ( -1 )
#define fastio ios_base::sync_with_stdio(false),cin.tie(NULL)
#define endl "\n"

using namespace std;


/// Edit distance


string str1 , str2;

int solve(int p1 , int p2){
    if(p2 == str2.size()) return 0;
    if(p1 == str1.size()) return str2.size() - p2;
    if(dpp[p1][p2] != -1) return dpp[p1][p2];
    int ans ;
    if(str1[p1] == str2[p2]) ans = solve(p1 + 1 , p2 + 1);
    else{
        ans = solve(p1 + 1 , p2) + 1; /// delete str1[p1]
        ans = min(ans , solve(p1 , p2 + 1) + 1); /// insert
        ans = min(ans , solve(p1 + 1 ,  p2 + 1) + 1) /// replace str1[p1] with str2[p2]
    }
    return dpp[p1][p2] = ans;
}

int main()
{
    cin>>str1>>str2;
    memset(dpp,-1,sizeof dpp);
    cout<<solve(0 , 0)<<endl;
}