Редакционное расстояние

Редакционное расстояние между двумя строками — это минимальное количество операций, необходимых для преобразования одной строки в другую. Разрешённые операции:

• Добавить один символ в строку.

• Удалить один символ из строки.

• Заменить один символ в строке.

Например, редакционное расстояние между и равно 2, так как сначала можно заменить на , а затем добавить .

Вам даны две строки, и ваша задача — вычислить их редакционное расстояние.

Ввод

Первая строка входных данных содержит первую строку, а вторая строка содержит вторую. Гарантируется, что количество символов в строках не превышает 1000.

Вывод

Программа должна вывести одно целое число — редакционное расстояние между двумя заданными строками.

Примеры