#include <bits/stdc++.h>
using namespace std;
int const MAX = 2002;
int const OO = (1 << 28);
char s1[MAX], s2[MAX];
int l1, l2;
int memo[MAX][MAX][2];
int DP(int i1, int i2, bool st) {
  if (i1 == l1) {
    return (l2 - i2);
  }
  if (i2 == l2) return 0;
  int &ref = memo[i1][i2][st];
  if (ref != -1) return ref;
  ref = l2 - i2;
  if (st) {
    ref = min(ref, DP(i1, i2 + 1, 1) + 1);
    ref = min(ref, DP(i1 + 1, i2, 1));
  }
  ref = min(ref, DP(i1 + 1, i2 + 1, 0) + (s1[i1] != s2[i2]));
  return ref;
}
int main() {
  scanf("%s%s", s1, s2);
  l1 = strlen(s1);
  l2 = strlen(s2);
  memset(memo, -1, sizeof(memo));
  cout << DP(0, 0, 1) << endl;
}
