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