while True:
    try:
        str1, str2 = input(), input()
        
        edit = [[i+j for j in range(len(str2) + 1)] for i in range(len(str1) + 1)]
        
        for i in range(1, len(str1) + 1):
            for j in range(1, len(str2) + 1):
                if str1[i - 1] == str2[ j - 1]:
                    d = 0
                else:
                    d = 1
                
                edit[i][j] = min(edit[i - 1][j] + 1, edit[i][j - 1] + 1, edit[i - 1][j - 1] + d)
        print(edit[len(str1)][len(str2)])
    except:
        break