#include <bits/stdc++.h>
int max(int a, int b) { return (a > b ? a : b); }
int min(int a, int b) { return (b > a ? a : b); }
int main(void) {
  char str1[2001], str2[2001];
  int i, j, len1, len2;
  int res, ans;
  scanf("%s", str1);
  scanf("%s", str2);
  len1 = strlen(str1);
  len2 = strlen(str2);
  res = 1000000;
  for (i = -1 * len2; i < len1; i++) {
    ans = 0;
    for (j = 0; j < len2; j++) {
      if (i + j < 0 || len1 < i + j || str1[i + j] != str2[j]) {
        ans++;
      }
    }
    res = min(ans, res);
  }
  printf("%d\n", res);
  return (0);
}
