Buscador de pel·lícules X14417

Per fer més suportables els dies de confinament, el professor Oak ha contractat una plataforma de televisió per Internet. Com que el catàleg de pel·lícules és inmens, el sistema proporciona un buscador que, mitjançant el control remot, permet buscar les pel·lícules pel seu títol. Més concretament, el buscador mostra a la pantalla de TV una matriu de lletres i un cursor a sobre d’una d’elles, inicialment la de la cantonada superior esquerra. Mitjançant els botons ↑, ↓, → i ← del control remot, es pot anar movent el cursor. Algunes de les caselles de la matriu, però, no es poden escollir (a la imatge, en vermell; en els jocs de prova, amb un asterisc *), i aleshores el cursor no es pot moure en aquella direcció. Tampoc no es pot sortir dels límits superior, inferior, dret i esquerre de la matriu. Una vegada el cursor és a sobre de la lletra desitjada, cal pitjar el botó OK.

Abans de mirar si una pel·lícula és al catàleg, el professor Oak vol saber quants botons del control remot li caldrà pitjar per inserir el títol al buscador. El podeu ajudar?

Per adaptar el problema a Jutge.org, a partir d’ara assumirem que les caselles de la matriu poden contenir una paraula (vista com una unitat) en lloc de només una sola lletra, i que el que inserim al buscador és doncs una seqüència de paraules, en lloc d’una seqüència de lletres.

Entrada

L’entrada conté diferents casos. Cada cas comença amb n el nombre de files i m el nombre de columnes de la matriu del buscador. Després segueixen n línies amb m paraules cadascuna, separades per espais. Les paraules consistents en un sol caràcter * representen caselles prohibides de la matriu. Llevat de *, que es pot repetir, la resta de paraules només poden aparèixer una sola vegada. Després segueix el nombre p de paraules de la seqüència que volem inserir al buscador. Finalment segueixen les p paraules de la seqüència, totes elles diferents de *. Qualsevol paraula de l’entrada està formada per lletres de l’alfabet en majúscula o guió baix _, o és la paraula *. Es compleix que 1 ≤ n, m ≤ 300, 1 ≤ p ≤ min(2 · n · m, 1000), i que per cada cas la cantonada superior esquerra no conté la paraula *.

Sortida

Per a cada cas, cal escriure en una línia el nombre total de cops que s’ha de pitjar un botó del comandament (↑, ↓, →, ← o OK) per tal d’inserir les p paraules de la seqüència al buscador. Si no és possible (perquè no es pot arribar a una paraula, o perquè no apareix a la matriu), cal escriure impossible.