Merkkijonon a ja b editointietäisyys on pienin määrä operaatioita, jolla a:n saa muutettua b:ksi. Sallitut operaatiot ovat:

• yhden merkin lisäys
• yhden merkin poisto
• yhden merkin muutos

Esimerkiksi merkkijonojen TALO ja PALLO editointietäisyys on 2.

Tehtäväsi on laskea annettujen merkkijonojen editointietäisyys.

Syöte

Syötteen ensimmäisellä rivillä on merkkijono a, jossa on n merkkiä väliltä A–Z.

Syötteen toisella rivillä on merkkijono b, jossa on m merkkiä väliltä A–Z.

Tuloste

Tulosta merkkijonojen editointietäisyys.

Rajat

• 1 \le n,m \le 5000

Esimerkki

Syöte:

TALO
PALLO

Tuloste:

2