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