// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



#define FOR(i,s, t) for(int i = s; i < t; i++)

#define ALL(a)  a.begin(), a.end()

#define SZ(x) (int)x.size()

#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define SORT(a) sort(ALL(a))

using VI = vector<int>;

using LL = long long;

using VVL = vector<vector<LL>>;

using VL = vector<LL>;



const LL LINF = 1e18;



int editDistance(string& s, string& t) {

	VVL dp(1010, VL(1010, 0));



	FOR(i, 0, 1010) {

		dp[i][0] = i;

		dp[0][i] = i;

	}

	FOR(i, 0, SZ(s)) {

		FOR(j, 0, SZ(t)) {

			int cost = (s[i] == t[j]) ? 0 : 1;

			dp[i + 1][j + 1] = min(dp[i][j] + cost, min(dp[i + 1][j] + 1, dp[i][j + 1] + 1));

		}

	}

	return dp[s.size()][t.size()];

}



signed main() {

	string s, t;

	cin >> s >> t;

	cout << editDistance(s, t) << endl;

}








// Optimized solution to the same problem (faster):
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;

typedef pair<int, int> pii;

typedef pair<ll, ll> pll;

const int INF = 1e9;

const ll LINF = 1e18;

template<class S,class T> ostream& operator << (ostream& out,const pair<S,T>& o){ out << "(" << o.first << "," << o.second << ")"; return out; }

template<class T> ostream& operator << (ostream& out,const vector<T> V){ for(int i = 0; i < V.size(); i++){ out << V[i]; if(i!=V.size()-1) out << " ";} return out; }

template<class T> ostream& operator << (ostream& out,const vector<vector<T> > Mat){ for(int i = 0; i < Mat.size(); i++) { if(i != 0) out << endl; out << Mat[i];} return out; }

template<class S,class T> ostream& operator << (ostream& out,const map<S,T> mp){ out << "{ "; for(auto it = mp.begin(); it != mp.end(); it++){ out << it->first << ":" << it->second; if(mp.size()-1 != distance(mp.begin(),it)) out << ", "; } out << " }"; return out; }



/*

 <url:>

 問題文============================================================

 =================================================================

 解説=============================================================

 

 ================================================================

 */





ll solve(){

    ll res = 0;

    string s1,s2; cin >> s1 >> s2;

    vector<vector<ll>> dp(s1.length()+1,vector<ll>(s2.length()+1,LINF));

    

    dp[0][0] = 0;

    for(int i = 0; i <= s1.length();i++) dp[i][0] = i;

    for(int j = 0; j <= s2.length();j++) dp[0][j] = j;

    

    for(int i = 1; i <= s1.length();i++){

        for(int j = 1; j <= s2.length();j++){

            dp[i][j] = min({dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+(s1[i-1]==s2[j-1]?0:1)});



        }

    }

    res = dp[s1.length()][s2.length()];

    return res;

}

int main(void) {

    cin.tie(0); ios_base::sync_with_stdio(false);

    auto ret = solve();

    cout << ret << endl;

    return 0;

}




// Fastest known solution for this problem:
#include<bits/stdc++.h>

using namespace std;

#define int long long

int editDistance(string x,string y){

  int n=x.length(),m=y.length();

  int INF=1LL<<55LL;

  vector<vector<int> > dp(n+1,vector<int>(m+1,INF));

  for(int i=0;i<=n;i++) dp[i][0]=i;

  for(int i=0;i<=m;i++) dp[0][i]=i;

  for(int i=1;i<=n;i++){

    for(int j=1;j<=m;j++){

      dp[i][j]=min(dp[i][j],dp[i-1][j]+1);

      dp[i][j]=min(dp[i][j],dp[i][j-1]+1);

      dp[i][j]=min(dp[i][j],dp[i-1][j-1]+(x[i-1]!=y[j-1]));

    }

  }

  return dp[n][m];

}

signed main(){

  string s1,s2;

  cin>>s1>>s2;

  cout<<editDistance(s1,s2)<<endl;

  return 0;

}