#include <bits/stdc++.h>
using namespace std;
string s1, s2;
int L1, L2;
int f[2000][2000];
int main() {
  cin >> s1 >> s2;
  L1 = s1.size();
  L2 = s2.size();
  int ans = L2;
  for (int i = L1 - 1; i >= 0; --i)
    for (int j = L2 - 1; j >= 0; --j)
      f[i][j] = (s1[i] == s2[j] ? 0 : 1) +
                ((i < L1 - 1 && j < L2 - 1) ? f[i + 1][j + 1] : 0) +
                (i == L1 - 1 ? L2 - 1 - j : 0);
  for (int i = 0; i < L2; ++i) ans = min(ans, i + f[0][i]);
  for (int i = 0; i < L1; ++i) ans = min(ans, f[i][0]);
  cout << ans << endl;
  return 0;
}
