#include <bits/stdc++.h>
using namespace std;
long long MAXi(long long a, long long b) { return a > b ? a : b; }
long long MINi(long long a, long long b) { return a < b ? a : b; }
int main() {
  string a, b;
  int ans = 1000 * 1000, x;
  cin >> a >> b;
  a = string(2001, '^') + a + string(2001, '^');
  for (int i = 0; i + b.size() <= a.size(); ++i) {
    x = 0;
    for (int j = 0; j < b.size(); ++j) x += (a[i + j] != b[j]);
    if (x < ans) ans = x;
  }
  cout << ans << "\n";
  return 0;
}
