#include <bits/stdc++.h>
int dp[2010][2010];
int len1, len2;
char s1[2010], s2[2010];
int cal(int ind1, int ind2);
int mini(int a, int b) {
  if (a < b) return a;
  return b;
}
int main() {
  int i, j, k, l, test, t = 1;
  scanf("%s", s1 + 1);
  scanf("%s", s2 + 1);
  len1 = strlen(s1 + 1);
  len2 = strlen(s2 + 1);
  memset(dp, -1, sizeof(dp));
  int ans = (1 << 28);
  for (i = len1; i > 0; i--) {
    ans = mini(ans, cal(i, len2));
  }
  printf("%d\n", ans);
  return 0;
}
int cal(int ind1, int ind2) {
  if (ind2 < 1) return 0;
  if (ind1 < 1) return ind2;
  if (dp[ind1][ind2] != -1) return dp[ind1][ind2];
  dp[ind1][ind2] = (1 << 28);
  if (s1[ind1] == s2[ind2]) dp[ind1][ind2] = cal(ind1 - 1, ind2 - 1);
  dp[ind1][ind2] = mini(dp[ind1][ind2], cal(ind1 - 1, ind2 - 1) + 1);
  if (ind1 == len1 || ind2 == len2)
    dp[ind1][ind2] = mini(dp[ind1][ind2], cal(ind1, ind2 - 1) + 1);
  if (ind1 == len1 || ind2 == len2)
    dp[ind1][ind2] = mini(dp[ind1][ind2], cal(ind1 - 1, ind2) + 1);
  return dp[ind1][ind2];
}
