#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9 + 7;
int prov(string& s, string& s1) {
  int counter = 0;
  for (int i = 0; i < s.size(); i++) {
    if (s[i] != s1[i]) counter++;
  }
  return counter;
}
int main() {
  string s, s1, fict;
  cin >> s >> s1;
  for (int i = 0; i < 2000; i++) fict += '$';
  s = fict + s + fict;
  int n = s.size(), m = s1.size();
  int minimal = inf;
  for (int i = 0; i < n - m + 1; i++) {
    string buffer = s.substr(i, m);
    if (prov(buffer, s1) < minimal) minimal = prov(buffer, s1);
  }
  cout << minimal << endl;
  return 0;
}
