#include <bits/stdc++.h>
using namespace std;
string s, t;
int ans = 30000;
int main() {
  cin >> s;
  cin >> t;
  for (int i = 0; i < 2000; i++) s = '#' + s;
  for (int i = 0; i < 2000; i++) s = s + '#';
  for (int i = 0; i < s.size() - t.size() + 1; i++) {
    string str = "";
    for (int j = 0; j < t.size(); j++) str += s[i + j];
    int cnt = 0;
    for (int j = 0; j < t.size(); j++)
      if (str[j] != t[j]) cnt++;
    ans = min(ans, cnt);
  }
  printf("%d", ans);
}
