#include <bits/stdc++.h>
using namespace std;
int main() {
  char a[6005], b[2005];
  for (int i = 0; i < 2000; i++) a[i] = '*';
  while (~scanf("%s%s", a + 2000, b)) {
    int lena = strlen(a), lenb = strlen(b);
    for (int i = lena; i < lena + 2000; i++) a[i] = '*';
    int mx = 0;
    for (int i = 0; i < lena; i++) {
      int sum = 0;
      for (int j = 0; j < lenb; j++) {
        if (b[j] == a[i + j]) sum++;
      }
      if (sum > mx) mx = sum;
    }
    printf("%d\n", lenb - mx);
  }
  return 0;
}
