import sys

COST_DEL = 1
COST_INS = 1
COST_SUBST = 1
COST_MATCH = 0

COST = []

def solve(s,t,flag = False):
  global COST
  sl = len(s)
  tl = len(t)
  COST = [[0 for i in range(tl+1)] for j in range(sl+1)]
  COST[0][0] = 0
  for i in range(1,sl+1):
    COST[i][0] = COST[i-1][0] + COST_DEL
  for i in range(1,tl+1):
    COST[0][i] = COST[0][i-1] + COST_INS
  for i in range(1,sl+1):
    for j in range(1,tl+1):
      c_d = COST[i][j-1] + COST_DEL
      c_i = COST[i-1][j] + COST_INS
      c_s = COST[i-1][j-1] + COST_SUBST
      if s[i-1]==t[j-1]: c_m = COST[i-1][j-1] + COST_MATCH
      else: c_m = sys.maxsize
      COST[i][j] = min(c_d, c_i, c_s, c_m)
  return COST[sl][tl]