#include <bits/stdc++.h>
const int INT_INF = 0x3f3f3f3f;
const int INT_M_INF = 0x7f7f7f7f;
const long long LL_INF = 0x3f3f3f3f3f3f3f3f;
const long long LL_M_INF = 0x7f7f7f7f7f7f7f7f;
const double pi = acos(-1.0);
using namespace std;
inline void debug(char ch) {
  for (int __ii = 0; __ii < 20; ++__ii) putchar(ch);
  printf("\n");
}
const double eps = 1e-8;
inline int dcmp(double a, double b) {
  if (fabs(a - b) < eps) return 0;
  return a < b ? -1 : 1;
}
const int dr[] = {0, 0, -1, 1, -1, -1, 1, 1};
const int dc[] = {-1, 1, 0, 0, -1, 1, -1, 1};
const int MAXN = 4000 + 10;
const int MAXT = 10000 + 10;
char s[MAXN], t[MAXN];
int main() {
  memset(s, 0, sizeof s);
  memset(t, 0, sizeof t);
  while (scanf("%s%s", s, t) == 2) {
    int slen = strlen(s), tlen = strlen(t), ans = 0;
    for (int i = 0; i < slen; ++i) {
      int num = 0;
      for (int j = 0; j < tlen; ++j)
        if (s[i + j] == t[j]) ++num;
      ans = max(ans, num);
    }
    for (int i = 0; i < tlen; ++i) {
      int num = 0;
      for (int j = 0; j < slen; ++j)
        if (t[i + j] == s[j]) ++num;
      ans = max(ans, num);
    }
    printf("%d\n", tlen - ans);
    memset(s, 0, sizeof s);
    memset(t, 0, sizeof t);
  }
  return 0;
}
