#include <bits/stdc++.h>
using namespace std;
char a[2005], b[2005];
int ans[2005][2005];
int main() {
  int i, j;
  scanf("%s", &a);
  scanf("%s", &b);
  int n = strlen(a);
  int m = strlen(b);
  for (i = 1; i <= m; i++) ans[0][i] = i - (a[0] == b[i - 1]);
  for (i = 1; i < n; i++) {
    for (j = 1; j <= m; j++) ans[i][j] = ans[i - 1][j - 1] + (a[i] != b[j - 1]);
  }
  int best = m, cur = 0;
  for (i = 0; i < n; i++) {
    for (j = 0; j <= m; j++) {
      cur = ans[i][j] + (m - j);
      if (cur < best) best = cur;
    }
  }
  printf("%d\n", best);
  return 0;
}
