Paraules barates P80225

Donada una matriu n × m amb lletres diferents, i una matriu associada que indica el cost de cada lletra, escriviu totes les paraules que comencen en una posició inicial donada, acaben a una posició final donada, i tenen un cost acumulat no superior a un màxim donat. Dins de la matriu podeu moure-us horitzontalment i verticalment, però sense repetir caselles.

Entrada

L’entrada consisteix en un sol cas, amb n i m, la matriu de lletres, la matriu de costs, la fila i columna de la posició inicial, la fila i columna de la posició final, i el cost acumulat màxim. Suposeu 1 ≤ n · m ≤ 52, i que tots els costs són enters entre 1 i 10⁶. Les files i columnes es numeren a partir de 0.

Sortida

Escriviu totes les paraules vàlides en qualsevol ordre.