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