#include <bits/stdc++.h>
using namespace std;
int main() {
  long i, j, k, s, e;
  char st1[2005], st2[2005];
  cin >> st1 >> st2;
  long l1 = strlen(st1), l2 = strlen(st2);
  s = -l2 + 1;
  long m = 70000, cur;
  while (s < l1) {
    cur = l2;
    for (i = 0, j = s; i < l2; i++, j++) {
      if (j >= 0 && j < l1) {
        if (st2[i] == st1[j]) cur--;
      }
    }
    if (cur < m) m = cur;
    s++;
  }
  cout << m;
  return 0;
}
