Palabras baratas P80225

Dada una matriz n × m con letras diferentes, y una matriz asociada que indica el coste de cada letra, escribid todas las palabras que empiezan en una posición inicial dada, acaban en una posición final dada, y tienen un coste acumulado no superior a un máximo dado. Dentro de la matriz os podéis mover horitzontalmente y verticalmente, pero sin repetir casillas.

Entrada

La entrada consiste en un solo caso, con n y m, la matriz de letras, la matriz de costes, la fila y columna de la posición inicial, la fila y columna de la posición final, y el coste acumulado máximo. Suponed 1 ≤ n · m ≤ 52, y que todos los costes son enteros entre 1 y 10⁶. Las filas y columnas se numeran a partir de 0.

Salida

Escribid todas las palabras válidas en cualquier orden.