#include<stdio.h>
#include<stdlib.h>
#include<stdint.h>
#include<inttypes.h>
#include<string.h>

typedef int32_t i32;

#define POS(i, j) ((i) * (n + 1) + (j))

void run (void) {
  const i32 max_len = 1000;
  char *a = (char *) calloc (max_len + 1, sizeof (char));
  char *b = (char *) calloc (max_len + 1, sizeof (char));
  scanf ("%s", a);
  scanf ("%s", b);
  const i32 m = strlen (a);
  const i32 n = strlen (b);
  i32 *dp = (i32 *) calloc ((m + 1) * (n + 1), sizeof (i32));
  for (i32 j = 0; j < n; ++j) {
    dp[POS(m, j)] = n - j;
  }
  for (i32 i = m - 1; i >= 0; --i) {
    dp[POS(i, n)] = m - i;
    for (i32 j = n - 1; j >= 0; --j) {
      if (a[i] == b[j]) {
	dp[POS(i, j)] = dp[POS(i + 1, j + 1)];
	continue;
      }
      i32 x = dp[POS(i + 1, j)];
      i32 y = dp[POS(i, j + 1)];
      i32 z = dp[POS(i + 1, j + 1)];
      i32 min = x < y ? x : y;
      dp[POS(i, j)] = 1 + (min < z ? min : z);
    }
  }
  printf ("%" PRIi32 "\n", dp[POS(0, 0)]);
}

int main (void) {
  run ();
  return 0;
}

