#include <bits/stdc++.h>
using namespace std;
const int max_n = 2002;
const int inf = (1 << 30);
int d[max_n][max_n];
char s1[max_n], s2[max_n];
int main() {
  scanf("%s", s1);
  scanf("%s", s2);
  int n = strlen(s1), m = strlen(s2);
  int mx = 0;
  for (int pos = (-m + 1); pos <= (n - 1); ++pos) {
    int st = max(0, pos);
    int en = min(n - 1, pos + m - 1);
    int cc = 0;
    for (int i = (st); i <= (en); ++i) {
      if (s1[i] == s2[i - pos]) ++cc;
    }
    mx = max(mx, cc);
  }
  printf("%d\n", m - mx);
  return 0;
}
