Sinulle on annettu kuvaus labyrintista, joka muodostuu seuraavista ruuduista:

• seinäruutu (#)
• lattiaruutu (.)
• alkukohta (@)
• loppukohta ($)
• avain (a–j)
• ovi (A–J)

Kaikki labyrintin reunaruudut ovat seinää. Voit liikkua labyrintissa pysty- ja vaakasuuntaisesti. Ovesta voi kulkea vain, jos sinulla on sitä vastaava avain. Voit pitää hallussasi rajattomasti avaimia samaan aikaan.

Mikä on pienin määrä askelia, joilla pääset alkukohdasta loppukohtaan?

Syöte

Syötteen ensimmäisellä rivillä on kaksi kokonaislukua n ja m: labyrintin korkeus ja leveys.

Sitten syötteessä on n riviä, joista jokaisella on m merkkiä. Nämä rivit kuvaavat labyrintin sisällön.

Tuloste

Tulosta yksi kokonaisluku: pienin askelten määrä.

Rajat

• 1 \le n,m \le 50

Esimerkki

Syöte:

8 10
##########
#...A.#$.#
#.###.##B#
#.#a#c##.#
#.#.#.#..#
#.#.#.#.##
#.@.#...b#
##########

Tuloste:

34