#include <bits/stdc++.h>
using namespace std;
const int NN = 2222;
const int INF = 1 << 29;
int dp[NN][NN][2];
string A, B;
int rec(int pos1, int pos2, int pre) {
  if (pos2 == ((int)B.size())) return 0;
  if (pos1 == ((int)A.size())) return ((int)B.size()) - pos2;
  int &res = dp[pos1][pos2][pre];
  if (~res) return res;
  res = INF;
  if (pre == 0) {
    res = min(res, rec(pos1 + 1, pos2, 0));
    res = min(res, rec(pos1, pos2 + 1, 0) + 1);
  }
  res = min(res, rec(pos1 + 1, pos2 + 1, 1) + (A[pos1] != B[pos2] ? 1 : 0));
  return res;
}
int main() {
  ios::sync_with_stdio(false);
  cin >> A >> B;
  int N = ((int)A.size());
  memset(dp, -1, sizeof(dp));
  int ans = rec(0, 0, 0);
  cout << ans << endl;
}
