#include <bits/stdc++.h>
using namespace std;
int f[2505 + 2505][2505 + 2505];
string s1, s2;
int l1, l2;
int main() {
  while (cin >> s1 >> s2) {
    s1 = string(2002, '@') + s1;
    l1 = s1.length();
    l2 = s2.length();
    for (int i = 0; i < 2010; i++) {
      for (int j = 0; j < i; j++) f[i][j] = 0x3f3f3f3f;
    }
    f[0][0] = 0;
    int ans;
    ans = 0x3f3f3f3f;
    for (int i = 1; i <= l2; i++) {
      for (int j = i; j <= l1; j++) {
        f[i][j] = f[i - 1][j - 1] + (s1[j - 1] != s2[i - 1]);
        ans = ((ans) < (l2 - i + f[i][j]) ? (ans) : (l2 - i + f[i][j]));
      }
    }
    printf("%d\n", ans);
  }
  return 0;
}
